Алгоритм получения кода Шеннона-Фоно

Выпишем исходный алфавит с вероятностями появления букв (4.5)

(4.13)

Горизонтальной линией разобьем этот столбец на такие две части, чтобы сумма вероятностей в обеих частях была приблизительно равной

α=Pα=0.5

β=P_β=0.23

γ=P_γ=0.20 (4.14)

Δ=P_Δ=0.06

Присвоим букве с наибольшей вероятностью значение «0» остальным «1».

(4.15)

Повторим выше приведенную операцию с другими вероятностями:

(4.16)

В результате получен код Шеннона – Фоно

Величина энтропии Н определяет среднюю нагрузку на один символ. Чем выше Н(х), тем больше информации несет один символ.

Выпишем сообщение (4.5) в новом коде:

0 10 0 110 0 10 0 110 0 111 0 10 0 110 0 10 110 0 110 0 111 0 10 0 110 0 10 0

α β α γ α β α γ α Δ α β α γ α β γ α β α Δ α β α γ α β α (4.17)

N₄=49 (4.18)

Т.е. вероятности равны, а для такого случая ранее было выведено

I=H_max (4.19)

Энтропия максимальна и следовательно код Шеннона-Фано позволил получить оптимальную нагрузку на символ, кроме того, для такого случая и скорость передачи информации по каналу связи также максимальна, т.к. для канала без шумов (3.13)

Z_c=H_i=H_max т.к. H_j(i)=0 (4.20)

Для канала же с шумами согласно (3.18) можно подобрать соответствующий код, для которого Z_c→Z_max.

Отметим еще одну особенность кода Шеннона-Фано, в нем нет необходимости вводить какие-либо различные знаки между символами. Такие коды, не требующие знаков разделения, называются разделительными.

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

Однако код Шеннона-Фано имеет недостаток. Он не помехоустойчивый, более того, искажение одного разряда (вследствие отсутствия разделительных символов) может вызвать искаженный прием нескольких символов.

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

Код Шеннона-Фано неизбыточный код, поэтому он не помехоустойчивый.

Дальше станет ясно, чтобы преобразовать неизбыточный код в помехоустойчивый необходимо добавить в код избыточные контрольные символы, позволяющие обнаружить искаженные символы и даже исправить, восстановить искаженный символ.

Код Грея.

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

Рис 1.11.

Для позиционной системы счисления, полное число получается, если суммировать все числа по разрядам:

(4.21)

Здесь i - номер разряда

n – количество разрядов

Для двоичного кода

(2⁰=1)

здесь n = число разрядов кода.

Число кодовых комбинаций n при n = 4

N=2ⁿ=2⁴=16

Для любой системы счисления

Здесь: n- число разрядов кода;

к - может меняться от 0 до m-1;

m - основание системы счисления.

Алгоритм образования кода Грея:

Десятичное число записывается его двоичным выражением по правилу:

здесь (4.22)

Так число N₁₀ = 26 тогда

N₂ = 1*2⁴+1*2³+0*2²+1*2¹+0*2⁰=11010

N₀ = 16+8-0+2+0

Код Грея образуется следующим образом:

единица старшего разряда остается без изменения, последующие разряды запишутся следующим образом:

если перед числом разряда (двоичного) стоит единица число (0,1) инвертируется, если нуль, остается без изменения, так 26 в коде Грея будет 10111.

Обратный перевод - также, первая единица (старший разряд) без изменения, далее, если сумма единиц предшествующего разрядов четна, разряд остается без изменения и инвертируется, если нечетна.

Дата добавления: 2014-01-06