Недвоичные коды

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

Коды, образованные по закону перестановок.

 Переустановки Р_н из g различных символов образуют кодовые комбинации, отличающиеся только порядком следования этих символов. Число элементов во всех комбинациях всегда одинаково. Так, если g=5, то есть a, b, c, d, e, то все эти символы всегда будут находиться в любой кодовой комбинации: авсde, bacde, cabed, becdea и т.д.

Длина слова n равна основанию кода g, то есть n=g. Отличительной особенностью этого кода является отсутствие одинаковых символов или букв в одном слове. Такой код часто называется аккордным. Общее число комбинаций N=n!

Например, при 3-х символах мы получим 6 комбинаций: abc, acb, bac, bca, cab, cba, (N=n!=1*2*3=6). При g=5 имеем N=5!=1*2*3*4*5=120.

Коды, образованные по закону переустановок, можно отнести к кодам с обнаружением одиночных и некоторых многократных ошибок. Действительно, на приеме искажение комбинаций делается очевидным, если в ее составе окажется несколько одинаковых символов, например aaabcd вместо aefbcd.

Частотные коды

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

Одночастотный код. В этом случае каждое сообщение передается радиоимпульсом определенной частоты, число слов N=g, где g - число частот. Во время передачи данной команды остальные частоты не передаются. Если имеется 4 частоты, то можно передавать только 4 сообщения.

Время и номера комбинаций

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

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

C²_g = g (g-1)

C²₄ = 4 (4 - 1) = 4*3 ₌6 - для 4-х частот (как для 4-х разрядов).

При последовательной посылке двух часто общее число кодовых комбинаций: А²_g= g(g - 1)

А²₄= 4(4-1)=12

Каждое сообщение передается комбинацией из двух частот, которые передаются одна после другой. По сравнению с предыдущим случаем, передача сообщений занимает в 2 раза больше времени. Однако число комбинаций оказывается в 2 раза большим, так как возможна передача сообщений перестановкой частот, например f₁ и f₂-однако сообщение, а f₁ и f_2-другое.

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

Код с проверкой на четность. Такой код образуется путем добавления к передаваемой комбинации, состоящей из к информационных символов неизбыточного кода, одного контрольного символа (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.

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

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

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

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

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

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

Код c5^2	Код c7^3
00011 00101 01010 11000	1010100 0101010 1110000 1001001

Наиболее употребляемыми являются пятиразрядный код с двумя единицами (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), имеющих такие значения, чтобы сумма единиц посылаемых в линию кодовых комбинаций была кратной трем. Примеры комбинаций такого кода представлены в таблице:

k	m	n = k+m
000110 100011 101011	10 00 11	00011010 10001100 10101111

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

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

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

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

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

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

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

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

k	m	Инверсный код n = k+m
110001 111101 111111 111100	1110001 1111101 0000000 0000011	11100011110001 11111011111101 11111110000000 11111000000011

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

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

2. При отсутствии ошибок в обеих группах символов их сумма будет равна нулю:

1) 1110001 2) 1100001 3) 1110001

1110001 0001110 1111001

0000000 1101111 0001000

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

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

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

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

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

Непомехозащищенные коды

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

Например, комбинации 0010 и 0011 отличаются друг от друга лишь в младшем разряде. Если помеха исказит первую комбинацию, то будет принят сигнал 0011 и будет принят сигнал и будет неясно, то ли пришла первая искаженная комбинация, то ли принята вторая неискаженная. Можно найти еще целый ряд комбинаций в том же коде, которые отличаются друг от друга только в одном разряде. Комбинации 0101 и 0111 - в 2-ом разряде комбинации 1110 и 0110 - в 4ом разряде и т.д. Есть различия в двух и больше разрядах, например, комбинации 1111 и 0001. Есть для каждой комбинации соседние комбинации, отличающиеся на один разряд: для 1111 имеем 0111, 1110, 1101, 1011. Все это делает двоичный код на все сочетания непомехозащищенным. Непомехоустойчивым или непомехозащищенным кодом называется код, в котором искажение одного разряда кодовой комбинации не может быть обнаружено. Иногда эти коды называются обыкновенными кодами. Рассмотрим примеры двоичных непомехозащищенных кодов.

Двоичный код на все сочетания. Этот код полностью выражается двоичной системой счисления. Общее число комбинаций N = 2ⁿ/

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

11 111 1111 - 234

111 11111 11 - 352

Например, в первой строке записано число 234, при записи равномерным кодом оно примет вид

0000000011 00000000111 0000001111

Двоично-десятичный код. Каждый разряд десятичного числа записывается в виде комбинации двоичного кода. Двоично-десятичный код, в котором каждый разряд десятичного числа записывается точным двоичным числом, обозначается 8-4-2-1. в этом случае каждый разряд двоичного числа выражается 2³-2²-2¹-2⁰.

Сотни Десятки Единицы

00 0000 0000 0 Число единиц, или «вес» кода, в каждой комбинации доходит до 3. Иногда применяются другие двоично-десятичные коды, например код 2-4-2-1, т.е. 2¹-2²-2^1-2⁰. Этот код удобен при его инвертировании, т.к. инвертированный код всегда дополняет основной до числа 9, что также в ряде случаев имеет значения. Например, если инвертировать 1011 (цифра 5), то получится комбинация 0100, соответствующая цифре 4.

00 0000 0001 1

00 0000 0010 2

00 0000 0011 3

00 0000 0100 4

00 0000 0101 5

00 0000 0110 6

00 0000 0111

7 00 0000 1000 8

00 0000 1001 9

00 0001 0000 10

00 0001 0001 11

00 0001 0010 12

00 0001 0011 13

00 1001 1001 99

01 0000 0000 100

01 0000 0000 101

01 1001 1001 199

11 1001 1001 399

Число-импульсный код. Иногда его называют единичным или унитарным кодом. Кодовые комбинации отличаются друг от друга числом единиц.

00000 - пример пятиразрядного кода. Очевидно N = n

10000

11000

11100

11110

11111

Код Морзе. Относится к числу неравномерных кодов, в которых кодовые комбинации отличаются различной длительностью. В коде Морзе сигналы (буквы и цифры, условные знаки) передаются в виде точек и тире. Точка может быть записана как 1 и передаваться одним импульсом. Тире записывается тремя строчными импульсами (без интервала между ними). Интервал между точкой и тире означает нули. Одна кодовая комбинация (буква или цифра) отдельна от другой интервалом из совокупности трех нулей. Если длительности 1 и 0 одинакова и равны τ, то самая короткая комбинация (буква Е) по продолжительности равна 4τ, а самая длительная - 22 τ (цифра 0). В среднем длина кодовой комбинации равна примерно 9, 5τ.

Различная длина кодовых комбинаций при передаче букв и цифр

А - 10111 (· - ) является недостатком кода Морзе, впервые

Н - 11101 ( - ·) примененного в 1844 году.

С - 10101 (· · ·)

Т - 111 (-)

1 - 1011101110111 (· - - - )

5 - 101010101 (· · · · ·)

Код Бодо. Равномерный пятиэлементный телеграфный код. Максимальное число комбинаций

N=2⁵=32

Код Бодо передается без разделительных знаков

А - 10000

Б - 00110

В - 01101

Г - 01010

Список литературы:

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки

2. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки

3. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение 

4. http://esis-kgeu.ru/

5. http://ru.wikipedia.org/