книги из ГПНТБ / Толстоусов, Г. Н. Прикладная теория информации учеб. пособие

п, - разрядная кодовая комбинация может быть представлена

ществуют только вершины. Расстоянием между двумя вершинами явля­ ется наименьшее число ребер куба, которые надо пройти, чтобы попасть из одной вершины в другую. Введем понятие вектора поме­ хи. При воздействии помехи кодовая комбинация искажается, т .ѳ . переходит из одной вершины в другую. Длина вектора помехи DaBна расстоянию между.этими вершинами. Рассмотрим случай единич­

69

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

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

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

образуется по правилу (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 ,

?Ф

а контрольное число вычисляться по формулам

лу 5 в двоичной системе.

В заключение отметим, что в коде "7.4" при появлении мно­ гократных ошибок контрольное число также может отличаться от нуля. Однако декодирование в этом случае будет проведено непра­ вильно, так как оно рассчитано на исправление лишь одиночных ошибок.

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

=I .

Другое важное свойство циклического кода заключается в том, что построение кодовой комбинации возможно путем умножения ком­

бинации первичного кода на некоторый порождающий полином

<Z(x):

А(х,)=А *(х) •С(х.).

Например, кодовая комбинация первичного кода А* = х. = ю при порождающем полиноме Сг(х) -= х + I образует следующую кодовую комбинацию циклического кода:

А(х)-A*(x)Qlx.) =xfxi-i)=x*-+x~ НО.

75

Эти свойства циклического кода приводят к сравнительно не­ сложным техническим средствам кодирования и декодирования, что объясняет широкое применение кода.

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

Определим операцию умножения. При умножении полиномов по обыч­ ным правилам с приведением подобных членов по модулю два может

76

/4(х)должны долиться на него без остатка, так как имеет мес­ то соотношение

А(ос.)~А*(х)'£(х).

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

Х А+ І=(х +і)(эс,^4-Х + *);

ВЫбйійМ

<т(х) = Х+1.

s

Пусть имеем первичную кодовую комбинацию

А*(х)= И -Х.+1,

77

тогда соответствующая комбинация циклического кода будет

A{x )=A"G=(x +'I)(x .+4)=X'*-+ X ч-х +4= Х*-+І= Л>/.

Можно убедиться, что остальные кодовые комбинации, полученные из ІОІ циклической перестановкой, будут делиться на(f-(x)~jc+S

без остатка. Следовательно, при Сг(х) - . £ + / кодовые комбина­ ции могут быть получены как с помощью циклической перестановки, так и с помощью умножения первичных комбинаций на порождающий полином.

Если порождающий полином не является делителем зоА+4 , а равен, например,

£(йС.)=Х ,

ТО при А*(х) в I I получим

А(х.)~(х.+і)х. - -НО.

Здесь кодовая комбинация ІОІ, получаемая циклической переста­

ко разных остатков будет получено при делении различных полино­

76