.Типы кодов

Все современные коды (рис. 3.42) делятся на безызбыточные (первичные) и избыточные (корректирующие).

Классификация кодов

Рис. 3.42. Классификация кодов

Коды, формирующие кодовые комбинации различной длины, называются неравномерными, а коды, которым соответствуют кодовые комбинации равной длины, —равномерными. В блочных кодах кодовые комбинации кодируются и декодируются независимо друг от друга. Избыточные блочные коды могут быть разделимыми и неразделимыми. В разделимых кодах роль разрядов кодовых комбинаций разграничена: часть разрядов, часто совпадающая с разрядами исходного первичного кода, является информационной, а остальные играют роль проверочных (контрольных) разрядов. В неразделимых кодах все разряды равноправные, и в кодовой комбинации нельзя отделить информационные разряды от проверочных. Примером блочного разделимого кода служит код с проверкой на четность. Его кодовая комбинация имеет вид xt х2... хк у. Первые к разрядов являются информационными и, как правило, совпадают с разрядами исходного первичного кода. Последний разряд является избыточным и определяется по формуле у = х, ©х2 ©...©хк. Таким образом, его значение зависит от того, четное или нечетное число единиц в кодовой комбинации. Если четное, то у = 0, в противном случае у = 1.

Кодирование как средство контроля передаваемой информации

При передаче кодированных сообщений между устройствами одной ЭВМ транспортировка кодов осуществляется по короткому пути. При передаче кодированных сообщений от одной ЭВМ к другой этот путь может оказаться длинным. При прохождении сообщения по каналу связи на него воздействуют помехи (рис. 3.43).

Общая схема передачи сообщений между ЭВМ

Рис. 3.43. Общая схема передачи сообщений между ЭВМ

При кодировании сообщений безызбыточными равномерными двоичными кодами длиной п используются все 2П возможных кодовых комбинаций, т.е. с любой из 2П кодовых комбинаций сопоставляется какой-либо символ внешнего алфавита. Изменение полярности одного или нескольких символов в какой-либо кодовой комбинации приводит к ошибочному ее декодированию. Наиболее опасными для кодированных сообщений являются импульсные помехи, под действием которых 0 может быть принят за 1, и наоборот (рис. 3.44).

Изменение кода сообщения под действием помех

Рис. 3.44. Изменение кода сообщения под действием помех

Пример. Передать по КС с помехами сообщения А, Б, В, Г, используя безызбыточное кодирование.

Для кодирования четырех сообщений выберем 2-разрядные двоичные коды, позволяющие образовать четыре различные КК, и присвоим сообщениям следующие коды: А — 00, Б — 01, В — 10, Г — 11.

Если под действием помехи один из элементов кодовой комбинации, например 00, соответствующий А, изменится, то она превращается (трансформируется) в другую разрешенную комбинацию, например 01, которую декодер интерпретирует как сообщение Б (рис. 3.45), и ошибка не будет обнаружена. И так может быть с каждой из четырех кодовых комбинаций.

Трансформация сообщения

Рис. 3.45. Трансформация сообщения

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

Помехоустойчивость избыточного кода обеспечивается благодаря тому, что для передачи информации используются не все 2П кодовых комбинаций равномерного кода, а лишь часть из них, получившая название разрешенных КК. Следовательно, число разрядов в КК должно быть таким, чтобы общее число комбинаций m = 2" превышало число разрешенных тр, используемых для передачи информации, т.е. m > nip.

Оставшаяся часть комбинаций m - mp, составляющая запрещенные КК, при передаче информации не применяется. В разрешенных комбинациях полярность элементов должна отличаться друг от друга, по крайней мере, в двух разрядах. Если в результате помех разрешенная комбинация превратится в запрещенную, то ошибка может быть обнаружена или исправлена. В подтверждение сказанному те же сообщения А, Б, В, Г закодируем трехразрядными двоичными комбинациями (п = 3), для чего из общего числа возможных КК m = 2 = 8 в качестве разрешенных шр выберем четыре с максимально отличающимися друг от друга разрядами и каждой из них поставим в соответствие одно из сообщений, например:

Остальные четыре комбинации (001, 010, 100, 111) относятся к запрещенным ш3.

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

Трансформация КК из разрешенной в запрещенную

Рис. 3.46. Трансформация КК из разрешенной в запрещенную

Следовательно, 3-разрядный двоичный код является помехоустойчивым и позволяет обнаруживать однократные ошибки в сообщениях А, Б, В, Г. Кратностью ошибки называют число искаженных символов в кодовой комбинации.

Для защиты сообщений А, Б, В, Г от двукратных ошибок избыточность КК необходимо увеличить, т.е. кодировать их более длинными кодовыми комбинациями, например 4-разрядными, выбрав при этом из общего числа возможных комбинаций (ш = 24) четыре разрешенных.

Конечно, и при избыточном кодировании ошибка может быть не обнаружена, если одна разрешенная комбинация трансформируется в другую разрешенную. Однако вероятность такого события гораздо меньше, чем вероятность превращения разрешенной комбинации в запрещенную, т.е. Pip^p < Pip_.

Существуют и другие способы обнаружения ошибок в кодовых комбинациях, например контроль на четность. В этом случае каждому из сообщений А, Б, В, Г ставится в соответствие кодовая комбинация, в которой сумма элементов по mod 2 с учетом избыточного контрольного разряда у равна 0, т.е. ©Xj © у = 0 , где х;,у е {0,1}.

Тогда любая кодовая комбинация, у которой эта сумма не равна О, будет считаться ошибочной. Значения функции сложения по mod 2 для двух переменных приведены в табл. 3.3.

Сложение по mod 2

Таблица 3.3

X,

х2

Х.ФХ,

0

0

0

0

1

1

1

0

1

1

1

0

Пример контроля на четность:

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >