Коды с обнаружением ошибок

Код с проверкой на четность. Такой код образуется путем добавления к передаваемой комбинации, состоящей из к информационных символов неизбыточного кода, одного контрольного символа (0 или 1), так чтобы общее число единиц в передаваемой комбинации было четным. Таким образом, общее число символов n в передаваемой комбинации:

n=k+1 В первом столбце приведены примеры

передачи отдельных комбинаций пятиразрядного двоичного кода на все сочетания (k – символы).

Во втором столбце к этим комбинациям приписывается контрольный символ 1, если сумма единиц в кодовой комбинации нечетная, или 0, если сумма единиц чётная. В нашем примере длина исходной кодовой комбинации k=5 позволяет при таком числе разрядов передать N=2⁵=32 кодовые комбинации. И хотя приписывание контрольного символа и увеличивает разрядность кода до n=6, число передаваемых комбинаций остаётся прежним. Поэтому общее число комбинаций.

N=2^n-1

Таким образом, этот код обладает избыточностью, т.к. в нашем примере вместо N=2⁶=64 комбинаций может быть послано только N=2^6-1=32 комбинаций.

В кодировании избыточности определяется отношением контрольных символов m к информационным k в одном слове:

(3-8)

Для пятиразрядного кода с проверкой на четность И=1/5. Очевидно, что чем длиннее кодовая комбинация, тем меньше избыточность и больше экономичность кода. Добавление контрольного символа увеличивает кодовое расстояние в передаваемых комбинациях от d=1 до d_min=2.

На приемной стороне производится так называемая проверка на четность. В принятых комбинациях подсчитывается количество единиц: если оно четное, считается, что искажений не было. Тогда последний контрольный символ отбрасывается и записывается первоначальная комбинация. Очевидно, что четное число искажений такой код обнаружить не может, т.к. число единиц при этом снова будет четным.

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

По изложенному принципу строится код с проверкой на нечетность.

Код с постоянным числом единиц и нулей в комбинациях (код с постоянным).

Общее число кодовых комбинаций в двоичном коде с постоянным весом равно: N=С^l_n= (3-9)

где l – число единиц в слове длиной n.

Наиболее употребляемыми являются пятиразрядный код с двумя единицами (N= c₅²=10) и саморазрядный код с тремя единицами (N= с₇³=35).

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

Правильность принятых кодовых комбинаций в кодах определяется путем подсчета количества единиц, и если, например, в коде с c₅² принято на две единицы, а в коде c₇³ не три единицы, то в передаче произошла ошибка. Очевидно, что код c₇³ может обнаружить все одиночные ошибки, т.к. в этом случае в комбинации будет либо две единицы, либо четыре. Кроме того, этот код позволяет обнаружить часть многократных ошибок ( двойные, тройные и т.п.), за исключением случаев, когда одна из единиц переходит в нуль, а один из нулей в единицу (такое двойное искажение называется смещением). При двойных смещениях (переход двух единиц в нуль и двух нулей в единицу) искажение также не обнаруживается.

Все сказанное правомочно и для кода c₅².

Распределительный код.Это также разновидность кода на определенное число сочетаний. В данном случае на сочетание c^l_n._. В любой кодовой комбинации длины n содержится только одна единица. Число кодовых комбинаций распределительного кода равно:

N=c^l_n=n (3-10)

Кодовые комбинации при n=6 можно записать: 000001, 000010, 000100, 001000, 010000, 100000.

Сложение по модулю 2 двух комбинаций показывает, что они отличаются друг от друга на кодовое расстояние d=2.

На рисунке показаны 3 кодовые комбинации: 100, 010, 001 для кода n=3. В системах телемеханики этот код нашел широкое применение из-за простой схемной реализации.

Код с числом единиц, кратным трем.Этот код образуется путем добавления к k информационным символам двух дополнительных контрольных символов (m = 2), имеющих такие значения, чтобы сумма единиц посылаемых в линию кодовых комбинаций была кратной трем. Примеры комбинаций такого кода представлены в таблице:

Такой код позволяет обнаружить все одиночные ошибки и любое четное количество ошибок одного типа (например, только переход 0 в 1). Не обнаруживаются двойные ошибки различных типов (т.е. смещения) и ошибки одного типа, кратные 3.

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

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

Каждый элемент двоичного кода на все сочетания передается двумя символами, причем 1 преобразуется в 10, а 0 в 01. Вместо комбинации 1010011 передается 10011001011010.

Таким образом, корреляционный код содержит вдвое больше элементов, чем исходный (И = 1). На примере ошибка обнаруживается в том случае, если в парных элементах будут содержаться одинаковые символы, т.е. 11 или 00 (вместо 10 и 01). При правильном приеме вторые (четные) элементы отбрасываются, и остается первоначальная комбинация.

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

Инверсный код. В таком коде для увеличения помехоустойчивости к исходной n-разрядной комбинации по определенному правилу добавляется еще n – разрядов. В линию посылается удвоенное число символов. Правило образования кода следующее: если в исходной комбинации четное число единиц, то добавляемая комбинация повторяет исходную, если нечетное, то в добавляемых разрядах все 0 превращаются в 1, а 1 в 0 (т.е. комбинация инвертируется по отношению к исходной). Пример:

Прием инверсного кода осуществляется в два этапа. На первом этапе суммируются единицы в первой основной группе символов k’ .

Если принятое число информационных k’ символов число четное, то контрольные символы m инвертируются. После этого на втором этапе контрольные символы m сравниваются с символами k’, и при наличии хотя бы одного несовпадения вся переданная комбинация n = k+m элементов бракуется. Это поэлементное сравнение эквивалентно сложению по модулю 2. При отсутствии ошибок в обеих группах символов их сумма будет равна нулю:

1) 1110001 2) 1100001 3) 1110001

111000100011101111001

0000000 1101111 0001000

нет ошибок есть ошибки есть ошибки

1) - нет ошибок, сумма равна нулю.

2) – ошибка в пятом разряде, код был проинвертирован, сумма теперь ≠0.

3) – Ошибка в четвертом разряде проинвертированного кода, сумма ≠0.

Обнаруживающие возможности инверсного кода достаточно велики. Этому, в частности способствует метод построения кода. Добавление m символов приводит к увеличению минимального кодового расстояния.