Помехоустойчивое кодирование командно-программной информации

Лекция 13

ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ КОМАНДНО-ПРОГРАММНОЙ ИНФОРМАЦИИ

Сущность помехоустойчивого кодирования цифровой информации заключается во введении (по определенному правилу) на передающей стороне канала связи определенной избыточности с целью последующего использования этой избыточности на приемной стороне для обнаружения ошибок и, если это возможно, то и исправления обнаруженных ошибок. При передаче командно-программной информации помехоустойчивое кодирование заключается в том, что вместе с h  информационными разрядами, обозначающими то или иное сообщение, по каналу связи дополнительно передается г = п - k проверочных символов, позволяющих обнаружить возможные ошибки в   п -разрядной кодовой комбинации. Таким образом, помехоустойчивый код отличается от обычного кода тем, что в канал могут быть переданы не все 2ⁿ   кодовых комбинаций, которые можно сформировать из имеющихся в распоряжении п  разрядов, а лишь некоторые из них, а именно 2^к  , обладающие определенным свойством и называемые разрешенными. Остальные неиспользуемые кодовые комбинации, число которых называют запрещенными. Таким образом, все множество N_общ = 2 ⁿкомбинаций разбивается на подмножества разрешенных( N_p = 2^k) и запрещенных ( N_з ) кодовых комбинаций.

Процесс кодирования схематично изображен на рис.12.7 где показано множество кодовых комбинаций (k ,k ) простого безызбыточного кода, у которого все k   разрядов каждой кодовой

k-k                                        n-k

о-разрешенные кодовые комбинации •-запрещенные кодовые комбинации

Рис.13.1

комбинации используются как информационные, и множество (n ,k ) кодовых комбинаций помехоустойчивого кода, у которого из общего числа разрядов п каждой кодовой комбинации лишь k разрядов являются информационными. Здесь же показаны разрешенные и запрещенные кодовые комбинации. В канал связи передаются только разрешенные комбинации. Из рис.13.1 видно, что искажение любого разряда безызбыточного кода приводит к трансформации одной разрешенной кодовой комбинации в другую (на рисунке это показано пунктирными стрелками на множестве простого ( k , k ) кода. В случае использования избыточного (n,k)-кода ошибка будет обнаружена в том случае, если она приводит к трансформации разрешенной кодовой комбинации в запрещенную [ траектория 2 на множестве(/n,k )-кода].С другой стороны,если ошибка приводит к трансформации одной разрешенной кодовой комбинации в другую (траектория 1),то она не может быть обнаружена. Коды, которые не только обнаруживают сам факт ошибки, но и указывают номер разряда кодовой комбинации, в котором произошла ошибка, называются кодами с исправлением ошибок.

Введением в кодовые комбинации определенного количества дополнительных г = п - k разрядов устанавливается нужное кодовое расстояние между комбинациями. При этом под кодовым(или хемминговым) расстоянием понимается минимальное число разрядов, в которых символы одной комбинации данного кода отличаются от символов другой кодовой комбинации. Например, кодовое расстояние между комбинациями 100110 и 0001II равно двум (отличие наблюдается в первом и последнем, т.е. в двух разрядах). В общем случае кодовое расстояние d=mind_ij=minSⁿ(x_ilÅx_jl)

где @ - знак, указывающий суммирование по mod 2;

i ,j - номера двух любых комбинаций данного кода;

I - номер разряда кодовой комбинации.

Величина кодового расстояния d  определенным образом связана с кратностью обнаруживаемых (m₀) и исправляемых( m_и ) ошибок. Ошибка не обнаруживается, если одна разрешенная кодовая комбинация в результате искажений преобразуется в другую разрешенную. Следовательно, для обеспечения обнаружения всех ошибок кратности до m₀ включительно необходимо, чтобы кодовое расстояние было

d₀=1+m₀

Для обеспечения возможности исправления'всех ошибок кратности до m_и включительно необходимо, чтобы принятая кодовая комбинация осталась в подмножестве, лежащем в окрестности переданной разрешенной кодовой комбинации. D_i>1+2m_и

Код, который может исправлять ошибки кратности m_и, может обнаружить ошибки кратности 2m_и

Кодовое расстояние, определяющее корректирующую способность кода, зависит от избыточности последнего, т.е. от количества проверочных разрядов г = п – k.

рис13.2

Таблица 12..3

Коды с d = 3 и 4, которые позволяют обнаруживать и исправлять одиночные ошибки или обнаруживать двойные и исправлять одиночные ошибки, в литературе обычно называют кодами Хемминга

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

Рис. 13.2

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

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