Файл: Толстоусов, Г. Н. Прикладная теория информации учеб. пособие.pdf

Процесс кодирования на передающем конце сводится к обра­ зованию, кроме информационной кодовой комбинации Сі , . . . , С* контрольных символов которые выражаются в виде линейной функ­ ции информационных символов:

данного вида кода.

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

образуется по правилу (15.I ) вторая группа контрольных символов

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

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

70

что позволяет по известному контрольному числу определить ме­

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

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

Код с четным числом единиц. Инверсный код. Рассмотрим не­ которые простейшие систематические коды, применяемые только для обнаружения ошибок. Одним из кодов подобного типа является код с четным числом единиц. Каждая комбинация этого кода содержит помимо информационных символов один контрольный символ, выбира­ емый равным 0 или I - так, чтобы сумма единиц в комбинации' всегда была четной. Примером могут служить пятиэначные комбина­ ции кода Бодо, к которым добавляется шестой контрольный символ: ІОІОЦ и 0X100,0. Правило вычисления контрольного символа можно

Это позволяет в декодирующем устройстве сравнительно просто производить обнаружение о'іэдйіок путем проверки на четность. На­ рушение четности имеет место при появлении однократных, трехкра­ тных и в общем случае ошибок нечетной кратности, что и дает возможность их обнаружить. Появление четных ошибок не изменяет четности суммы (15 .4), поэтому такие ошибки не обнаруживаются,

К достоинствам кода следует отнести простоту кодирующих и

71

декодирующих устройств, а также малую избыточность jU=4f(-l+K) » однако последнее определяет и его основной недостаток - сравни­ тельно низкую корретирующую способность.

Значительно лучшими корректирующими способностями обладает инверсный код, который также применяется только для обнаружения ошибок. С принципом построения такого кода удобно ознакомиться на примере двух комбинаций: 11000,11000 и 01101,10010. В каждой комбинации символы до запятой являются информационными, а после­ дующие - контрольными. Если количество единиц в информационных символах четное, то контрольные символы представляют собой про­ стое повторение информационных. В противном случае, когда число

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

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

ко те ошибки четвертой кратности, которые искажают одинаковые номера информационных и контрольных символов. Например, если передана комбинация 10100,10100, а принята 10111,10111, то та­

однако она достигается ценой сравнительно большой избыточности,

72

вые четыре места, то последующие три контрольных символа обра­ зуются по общему правилу (15.I) как суммы:

ej =оС}1с, Q tL ji сх © ot^ C l© оLjvC„. (G *)

Декодирование осуществляется путем трех проверок на четность

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

венно одно из трех значений: 100, 010 или 001. Остальные четы­ ре контрольных числа используются’ для выявления* ошибок в инфор­ мационных символах. Порядок присвоения контрольных чисел оши - бочным информационным сиволам может устанавливаться любой, на­ пример, как показано в табл. 15 .I . Нетрудно показать, что это­ му распределению контрольных чисел соответствуют коэффициенты

73

Таблица 15.2

столбцами табл. 15 .2. Это свойство дает возможность при выбран­

тот символ кодовой комбинации, который претерпел искажения. Исправление искаженного символа двоичной системы состоит в про­ стой замене 0 на I или I на 0.

Здесь был рассмотрен простейший способ построения и деко­ дирования кодовых комбинаций, в которых первые места отводились информационным символам, а соответствие между контрольными чи­ слами и ошибками определялось таблицей. Вместе с тем существует более изящный метод отыскания одиночных ошибок, предложенный впервые самим Хеммингом. При этом методе код строится так, что контрольное число в двоичной системе счисления сразу указывает номер искаженного символа. Правда в этом случае контрольные символы необходимо располагать среди информационных, что усло­ жняет процесс кодирования. Для кода »7.Ф" символы в комбинации должны размещаться в следующем порядке:S^e^C^e^C^-CgCf ,

?Ф