Теория кодирования

Если N₀ = 2ⁿ - общее число кодовых комбинаций, а N = 2^k - число разрешенных, то число запрещенных кодовых комбинаций равно

N₀-N = 2ⁿ -2^k.

При этом число ошибок, которое  приводит к запрещенной кодовой  комбинации равно:

, (1)

где S - кратность ошибки, т. е. количество искаженных символов в кодовой комбинации S = 0, 1, 2, ...

C_nⁱ - сочетания из n элементов по i, вычисляемое по формуле:

, (2)

для S = 0 ;

S = 1 ;

S = 2 ;

S = 3 ; и т. д.

Для исправления S ошибок количество комбинаций кодового слова, составленного из m проверочных разрядов N = 2^m, должно быть больше возможного числа ошибок (2), при этом количество обнаруживаемых ошибок в два раза больше, чем исправляемых

(3)

2^m ³ откуда .

Для одиночной  ошибки, как наиболее вероятной  .

В зависимости  от исходных данных кода (n или k) можно использовать

формулы

.

При этом, m = [log₂(1+n)] или m = [log₂ {(k+1)+ [log₂(k+1)]}], где ква-дратные скобки обозначают округление до большего целого.

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

Для исправления  двукратной ошибки

 или  .

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

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

Код  с  постоянным   весом  это  код, который содержит постоянное число единиц и нулей. Число кодовых комбинаций составит

Пример 1. Коды с двумя единицами из пяти и тремя единицами из семи.

11000 10010 00101	0000111 1001001 1010100

 

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

 Рассмотрим код с тремя  единицами из семи. Для этого  кода возможны смещения трех  типов.

                   

Вероятность появления не обнаруживаемых ошибок смещения

, где   

При p<<1     , тогда  

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

Вероятность обнаруживаемых ошибок     . Тогда коэффициент обнаружения будет равен  

Например,  код     при         коэффициент обнаружения составит      ,  избыточность      L=27%. 

3.4.Распределительный код

Это также разновидность кода на определенное число сочетаний. В данном случае на сочетание 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. В системах телемеханики этот код нашел широкое применение из-за простой схемной реализации.

3.5. Код с проверкой на четность

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

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

k	m	n = k+m
11011 10101 00010 11011 11111	0 1 1 0 1	11011 0 11011 1 00010 1 11101 0 11111 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.

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

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

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

Пример 1.

Построим коды для проверки на четность, где k - исходные комбинации, r - контрольные символы.   

k	r	n
11011	0	110110
11100	1	111001

 

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

         

Так как вероятность ошибок     является весьма малой величиной, то можно ограничится                     

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

При передаче большого количества кодовых  комбинаций N_k , число кодовых комбинаций, в которых ошибки обнаруживаются, равно:       

Общее количество комбинаций с обнаруживаемыми  и не обнаруживаемыми ошибками равно  

Тогда коэффициент обнаружения K_обн для кода с четной защитой будет равен

 

Например, для кода с  k=5   и вероятностью ошибки       коэффициент обнаружения составит       . То есть 90% ошибок обнаруживаем, при этом избыточность будет составлять           или 17%. 

3.6. Код с числом единиц кратным трем

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

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

двойные ошибки разных типов (смещения) и ошибки одного типа, кратные

трем. На приемной стороне полученную комбинацию проверяют  на кратность

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

код обладает дополнительной возможностью обнаруживать ошибки: если

первый контрольный  символ равен нулю, то и второй тоже должен быть равен нулю.

 

3.7. Код с удвоением элементов(корреляционный код)

В рассматриваемом  коде символы исходного кода кодируются повторно. Правило

вторичного  кодирования таково: если в исходном кодовом слове на какой-либо

позиции стоит 0, в новом помехоустойчивом коде на эту позицию записывается пара символов 01, а если в  исходном коде была 1, она записывается как 10.

Например, кодовое  слово 1001 в корреляционном коде будет  выглядеть следующим образом: 10010110. Корреляционный код будет всегда иметь вдвое

больше элементов, чем исходный. Поэтому его коэффициент  избыточности

всегда равен 0,5:

На приеме ошибка обнаруживается в том случае, если в парных элементах

содержатся  одинаковые символы, т.е. 11 или 00 (вместо 10 и 01). При правильном приеме вторые (четные) элементы отбрасываются и  остается первоначальная комбинация.

Код обладает сравнительно высокой помехоустойчивостью, поскольку

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

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

 

3.8. Инверсный код

Это разновидность кода с двукратным повторением. При использовании данного кода комбинации с четным числом единиц повторяются в неизменном виде, а комбинации с нечетным числом единиц – в инвертированном.

 Примеры представления кодовых комбинаций в инверсном коде приведены в таблице.

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

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

В первом варианте принята комбинация 111010111010. В первой половине кодового слова (информационных символах) четное количество единиц, поэтому производится ее суммирование по модулю 2 с неинвертируемыми контрольными символами r, что в результате дает нулевую сумму, т.е. комбинация принята без искажений.

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

В третьем  варианте принята комбинация 111010101010. Поскольку в информационной последовательности четное количество единиц, при проверке контрольные символы суммируются с информационными без инверсии. В этом

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