vopros-otvet (519806), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

Рис. 3.2. Кодовое дерево

Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию:

.

Рассмотрев методики построения эффективных кодов, нетрудно убедиться в том, что эффект достигается благодаря присвоению более коротких кодовых комбинаций более вероятным буквам и более длинных менее вероятным буквам. Таким образом, эффект связан с различием в числе символов кодовой комбинации.

А это приводит к трудности при декодировании.

Метод Шенона:

Код строится следующим образом: буквы алфавита сообщения выписываются в таблицу в порядке убывания вероятностей. Затем они разбиваются на две группы так, чтобы суммы вероятностей в каждой из групп были бы по возможности одинаковы.

Всем буквам верхней половины в качестве первого символа приписывается 0, а всем нижним 1, или наоборот, это не принципиально, но правило должно оставаться до завершения кодирования всех букв.

Каждая из полученных групп в свою очередь разбивается на две подгруппы с одинаковыми суммарными вероятностями и так далее. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется 3 символа.

Наибольший эффект сжатия получается в случае, когда вероятности букв представляют собой целочисленные отрицательные степени двойки. Среднее число символов на букву в этом случае точно равно энтропии источника.

Убедимся в этом. Рассмотрим алфавит:

Таблица 3.1

Буквы	Вероятность	Кодовые комбинации
Z1	1/2	1	1
Z2	1/4	01	1	2
Z3	1/8	001		2	3
Z4	1/16	0001			3
Z5	1/32	00001
Z6	1/64	000001
Z7	1/128	0000001
Z8	1/128	0000000

Вычислим энтропию алфавита:

Вычислим среднее число символов на букву по формуле:

.

В более общем случае для алфавита из 8 букв среднее число символов на букву будет меньше 3, но больше энтропии алфавита H(Z).

В общем случае:

H(Z) ≤ l ≤ log₂M,

.

28. Техническая реализация кодирующего и декодирующего устройств эффективного кода.

Кодер источника должен содержать в себе следующие блоки:

• устройство декорреляции, ставящее в соответствие исходной последовательности букв другую декоррелированную последовательность букв;

• собственно кодирующее устройство, ставящее в соответствие декоррелированной последовательности букв последовательность кодовых комбинаций;

• буферное устройство, выравнивающее плотность символов перед их поступлением в линию связи.

Декодер источника соответственно должен содержать:

• устройство декодирования последовательности кодовых комбинаций в последовательность букв;

• буферное устройство, выравнивающее интервалы между буквами;

• устройство рекорреляции, осуществляющее операцию обратную декорреляции.

В частном случае, когда корреляционные связи между буквами отсутствуют и имеется возможность управлять моментами считывания информации с источника, схемы кодера и декодера источника существенно упрощаются.

Ограничимся рассмотрением этого случая, применительно к коду, полученному по методике Хаффмена в предыдущем примере.

Рассмотрим схемы кодирующего и декодирующего устройств на примере нижеприведенных кодовых комбинаций, полученных в параграфе 3.3.2.

Таблица 3.6

Буква	код
Z1	01
Z2	00
Z3	111
Z4	110
Z5	100
Z6	1011
Z7	10101
Z8	10100

Схема кодера источника приведена ниже. В ней можно выделить основной матричный шифратор 1 с регистром сдвига 1 и вспомогательную схему управления считыванием информации, содержащую матричный шифратор 2 с регистром сдвига 2. Число горизонтальных шин шифраторов равно числу кодируемых букв, а число вертикальных шин в каждом их них равно числу символов в самой длинной комбинации используемого эффективного кода.

Рис. 3.3. Схема кодера

Включение диодов в узлах i-ой горизонтальной шины основного шифратора 1 обеспечивает запись в регистр сдвига 1 кодовой комбинации, соответствующей букве Z_i.

Во вспомогательном шифраторе 2 к каждой i-ой горизонтальной шине подключен только 1 диод, обеспечивающий запись единицы в такую ячейку регистра 2, номер которой совпадает с числом символов в кодовой комбинации, соответствующей букве Z_i.

Кодирование очередной буквы Z_i, выдаваемой источником информации, осуществляется посредством подачи через схему совпадения & импульса на i-ю горизонтальную шину обоих шифраторов единицы с выхода из регистра 2, соответствующей окончанию кода предыдущей буквы, и единицы с одной из активных шин источника информации (А₁÷ А₈).

При этом в регистр сдвига 1 записывается кодовая комбинация, соответствующая букве Z_i, а в регистр 2 единица, несущая информацию о длине этой кодовой комбинации. Продвигающими импульсами с генератора (ГИ), записанная в регистре 1, кодовая комбинация символ за символом выталкивается в линию связи. Посредством того же генератора сдвигается и единица в регистре 2. Соответствующий этой единице импульс появится на выходе регистра 2 в тот момент, когда из регистра 1 будет вытолкнут последний символ кодовой комбинации. Этот импульс используется как управляющий для перехода к кодированию следующей буквы.

Декодер:

Рис. 3.4. Схема декодера

Символы декодируемой кодовой комбинации, поступающие на вход регистра, начиная со старших разрядов, продвигаются по нему импульсами тактового генератора (ГИ), работающего синхронно с генератором импульсов кодирующего устройства. Поскольку некоторые из кодовых комбинаций начинаются с нуля или нескольких нулей , то непосредственно по содержанию регистра сдвига невозможно определить начало этих комбинаций, а следовательно, и правильно их декодировать.

Для однозначного определения начала каждой кодовой комбинации число ячеек регистра берется на единицу больше числа символов в самой длинной комбинации используемого эффективного кода. В дополнительной ячейке Т₆ регистра сдвига перед поступлением в него очередной декодируемой комбинации всегда записывается единица. В нашем примере максимальная длина кодовой комбинации равна 5-ти символам. Дополнительная единица увеличивает максимальную длину кодовой комбинации до 6-ти символов, а регистр сдвига дешифратора содержит 7 тригеров. (Последний тригер Т₀ не используется ни в одной кодовой комбинации, а потому он может быть исключен из рассмотрения или ему во всех кодовых комбинациях можно присвоить нулевое состояние.) Продвигаясь по регистру, она сигнализирует о начале кодовой комбинации, а следовательно, и о ее длине. Матричный дешифратор построен в соответствии с комбинациями используемого кода, к которым со стороны старшего разряда приписана лишняя единица.

У каждого тригера дешифратора имеются две шины. Если тригер находится в нулевом состоянии, то высокий потенциал имеет место на левой шине, а на правой ноль. Если тригер находится в состоянии единицы, то наоборот, на правой шине 1, а на левой 0. Для приема соответствующей буквы необходимо диоды устанавливать в соответствии с принимаемой кодовой комбинацией. Например, букве Z₁ соответствует код 01. На дешифраторе в регистре сдвига это будет соответствовать 1010000, что показано в верхней строке дешифратора.

Рис. 3.5. Состояние ячеек регистра для кодовой комбинации Z₁

Кодовой комбинации Z₆ (1011) будет соответствовать запись в регистре сдвига 1101100, так как коды букв приходят, начиная со старшего разряда. Состояние ячеек регистра показано на рис. 3.6.

Рис. 3.6. Состояние ячеек регистра для кодовой комбинации Z₆

При поступлении в регистр последнего символа декодируемой кодовой комбинации, срабатывает соответствующая схема "И" (&), что приводит к зажиганию соответствующей лампочки в блоке индикации и к установке регистра сдвига в начальное состояние через схему "ИЛИ" (в правой ячейке Т₆ – единица, в остальных – ноль).

29. Теорема Шеннона о пропускной способности канала без помех и

следствие из нее. Способы сжатия информации.

В любом реальном сигнале всегда присутствуют помехи. Однако, если их уровень настолько мал, что вероятность искажения практически равна нулю, можно условно считать, что все сигналы передаются неискаженными. В этом случае среднее количество информации, переносимое одним символом, можно считать:

J(Z; Y) = H_апр(Z) – H_апост(Z) = H_апр(Y),

так как H(Y) = H(Z) и H(Y/Z) = 0, а max{J(Z; Y)} = H_max(Y) – max энтропия источника сигнала, получающаяся при равномерном распределении вероятностей символов алфавита Y.

p( y₁) = p( y₂) = ... = p( y_m) = 1/M_y,

т.е. H_max(Y) = log_aM_y

и, следовательно, пропускная способность дискретного канала без помех в единицах информации за единицу времени равна:

C_y = V_y · max{J(Z; Y)} = V_y · H_max(Y) = V_y · log_aM_y

Характеристики

Список файлов ответов (шпаргалок)