КОДИРОВАНИЕ 6

Работа добавлена на сайт samzan.net:

6. КОДИРОВАНИЕ

6.1  Основные понятия

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

Канал передачи имеет свой язык и алфавит. Язык канала задают исходя из требований дальности, помехоустойчивости, быстродействия, секретности и т. п. Алфавит канала определяется набором возможных физических состояний сигнала — например, положительной и отрицательной полярностью импульсов напряжения, импульсами тока различной частоты и др.

Для передачи информации алфавит и язык исходного сообщения необходимо поставить в соответствие алфавиту и языку канала. Процесс преобразования дискретного сообщения из одного языка в другой называют  кодированием, а правило, по которому осуществляется это преобразование, — кодом. Общее число символов m, используемых для кодирования, называют основанием кода, а комбинации символов — кодовыми комбинациями. Число символов n, образующих кодовую комбинацию, называют ее длиной. В качестве символов используют цифры, буквы, арифметические или другие знаки. Так, при записи цифрами 1 и 0 (т. е. m = 2) кодовая комбинация при n = 5 может иметь вид, например, 10011.

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

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

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

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

Ошибки в канале связи могут быть независимыми (некоррелированными, и зависимыми (коррелированными). В первом случае отдельные ошибки статистически не зависят друг от друга, во втором — каждая очередная ошибка статистически зависит от предыдущих. Зависимые ошибки могут возникать группами («пакетами»).

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

6.2 Безызбыточные коды

Числовые коды. Такие коды получили большое распространение в связи с развитием цифровых методов обработки информации. Они строятся по законам образования систем счисления. При этом основание кода соответствует основанию системы счисления m. Так, в десятичной системе m = 10, т. е. в ней используются 10 цифр — от 0 до 9. В двоичной системе m = 2 и соответственно имеются только две цифры — 0 и 1.

С помощью цифр записывается любое число. Место цифры в числе называют разрядом. Значение («вес») разряда определяется основанием m и порядковым номером разряда. При записи числа цифры располагают слева направо от высших разрядов к низшим. При этом каждое n-разрядное число N можно представить в виде:

,

где 0 ≤ Ki ≤ m – 1 цифра соответствующей системы счисления.

Например, десятичное число 1703 (m = 10, n = 4) можно записать .

То же число в двоичной системе будет иметь вид:  .

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

Единичный код имеет один символ — 1 (единицу). Значение числа определяется количеством единиц. Так, числу 1 соответствует кодовая комбинация 1, числу 2 — комбинация 11, числу 3 — 111 и т. д. Код некомплектный, так как число элементов в комбинациях неодинаково. Добавление или подавление помехой одного элемента приводит к ошибке, наличие которой невозможно обнаружить. Несколько увеличить помехозащищенность кода можно, дополнив его до некоторого постоянного числа символов нулями (т. е. сделав его комплектным) и обеспечив контроль по числу элементов в кодовой комбинации. При этом данный код становится вариантом избыточного двоичного кода с низкой помехозащищенностью (ошибки типа 0 → 1 и 1 → 0 не обнаруживаются).

Двоичный код наиболее широко применяется в технике, так как он соответствует двоичной природе многих событий и явлений. Операции с двоичными числами достаточно просты. Число возможных комбинаций N =2n. Ряд двоичных чисел представлен в табл.6.1.

Двоичные коды машинных слов ЭВМ содержат до 32 разрядов. Запись их довольно громоздка и ненаглядна, что может приводить к ошибкам. Поэтому часто пользуются записью двоичного кода в восьмеричной или шестнадцатеричной системе счисления, вторая является наиболее короткой и удобной. При этом безызбыточные комбинации двоичного кода разбивают на четырехразрядные группы — тетрады. Каждую из них обозначают соответствующей шестнадцатеричной цифрой. Например, двоичная комбинация 1001 1000 1101 1111 в шестнадцатеричной системе записи примет вид: 9 8 DF.

Таблица 6.1

Десятичное число	Двоичное четырехразрядное число	Форма записи шестнадца-теричного числа	Комбинация кода Грея, соответствующая десятичному числу	Десятичное число	Двоичное четырехразрядное число	Форма записи шестнадца-теричного числа	Комбинация кода Грея, соответствующая десятичному числу
0	0000	0	0000	8	1000	8	1100
1	0001	1	0001	9	1001	9	1101
2	0010	2	0011	10	1010	A	1111
3	0011	3	0010	11	1011	B	1110
4	0100	4	0110	12	1100	C	1010
5	0101	5	0111	13	1101	D	1011
6	0110	6	0101	14	1110	E	1001
7	0111	7	0100	15	1111	F	1000

Нечисловые двоичные коды. Известны двоичные коды, в которых «вес» цифры в разряде в различных комбинациях не остается постоянным. К ним относятся, например код Грея и оптимальный код Шеннона-Фано.

В коде Грея две соседние комбинации отличаются не более чем в одном разряде. Код Грея выполняется в соответствии с правилом: если в комбинации безызбыточного двоичного кода в старшем разряде по отношению к рассматриваемому стоит 0, то при переходе к коду Грея его символ сохраняется; если же стоит 1 — меняется на обратный. Пусть, например, дана комбинация двоичного кода 01001. Преобразуем ее в комбинацию кода Грея. В младшем разряде двоичного числа — 1, во втором — 0. Поэтому в коде Грея сохраняется символ 1. В следующем разряде двоичного кода стоит также 0, соответственно в коде Грея запишем 0. В четвертом разряде двоичного кода находится 1, поэтому в коде Грея изменим символ на 1. Следующий символ сохраняет значение. Таким образом получаем комбинацию 1101.

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

Каждый сектор условно разделен на части, число которых равно числу разрядов. Если в разряде комбинации имеется I, то в соответствующей части сектора пробивается отверстие. Установив с разных сторон такой маски источник света и фотоприемник, можно угол поворота диска преобразовать в код. При считывании информации, когда диск находится на границе перехода от одной комбинации в другую, при использовании простого двоичного кода возможны большие погрешности за счет того, что вследствие незначительных неточностей в изготовлении одна часть считанных разрядов будет принадлежать одной комбинации, а другая часть — смежной комбинации. Так, при переходе от числа 3 (011) к числу 4 (100) могут быть получены комбинации двоичного кода 000, 111 и др. В коде Грея при переходе к смежной комбинации меняется только один элемент: числу 3 соответствует комбинация 0010, числу 4— 0110. Поэтому на границе между комбинациями будет передаваться или то, или другое число. Таким образом дополнительно ошибки по отношению к ошибке квантования не возникает.

Код Шеннона-Фано — это неравномерный код. При его построении учитывается вероятность появления определенных сообщений (или соответствующих им комбинаций). Тем сообщениям, вероятность которых велика, приписываются кодовые комбинации с малым числом элементов. Сообщениям с малой вероятностью приписываются комбинации с большим числом символов:

Номер сообщения	1	2	3	4	5	6	7	8
Вероятность сообщения……	0,22	0,2	0,18	0,15	0,1	0,08	0,05	0,02
Кодовая комбинация…	00	01	100	110	101	1110	11110	11111

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

Так, в рассмотренном примере в одну группу войдут сообщения 1 и 2, в другую 3—8. В кодовой комбинации сообщений в старший разряд первой группы записывают 0, а в старший разряд второй группы — 1. Далее каждая группа вновь делится на две части и по тому же правилу в кодовые комбинации полученных подгрупп записывают второй элемент: 0 — в нечетные подгруппы, 1 — в четные и т. д.

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

Составные коды. Эти коды основаны на использовании двух и более различных законов образования. К ним относится широко распространенный двоично-десятичный код. Он принадлежит к группе кодов, которые благодаря двоичному характеру символов (или сигналов) позволяют осуществить легкий переход к десятичной системе. В этом коде каждая цифра от 0 до 9 десятичного числа записывается четырехразрядным двоичным числом. При этом возможно N = 24 = 16 различных комбинаций. Для обозначения 10 цифр служат 10 из них. В принципе можно использовать любые комбинации из 16. Наибольшее применение нашел двоично-десятичный код, в котором десятичные цифры обозначаются соответствующими им комбинациями натурального ряда двоичных чисел. Такой код называют кодом типа 8, 4, 2, 1 — по весу разрядов в двоичном числе. Например, число 325 запишется следующим образом: 0011—0010—0101. Передача разделительных знаков между тетрадами при комплектном коде не обязательна, так как каждый разряд содержит одинаковое число символов.

Возможны и другие виды двоично-десятичных кодов, например, 2, 4, 2, 1:

Десятичная цифра……….	0	1	2	3	4	5	6	7	8	9
Код 2, 4, 2, 1	0000	0001	0010	0011	0100	1011	1100	1101	1110	1111

При этом число 325 запишется в виде: 0011—0010—1011. Цифры 9, 8, 7, 6 и 5 записываются в инверсном виде по отношению к цифрам 0, 1, 2, 3 и 4. Код позволяет упростить двоично-десятичные счетчики за счет суммирующего счетчика, который до четвертого импульса работает обычным образом. На пятом импульсе все его триггеры переключаются обратно и далее он вновь работает, как обычный суммирующий счетчик.

Коды, применяемые в телеграфии и при передаче данных. Код Морзе служит для передачи сообщений вручную. Перед вручением адресату сообщение необходимо дешифрировать. Автоматическая дешифрация и защита от искажений неравномерных кодов сложны. Поэтому были разработаны комплектные телеграфные коды, из которых широко применяют пятиэлементный код Бодо. Весь алфавит в этом коде разделен на четыре группы по семь букв (символов). Код группы — двухразрядный: 00, 10, 01, 11. Внутри каждой группы символы кодируются трехразрядными двоичными числами: 100, 010, 001, 110, 101, 011, 111. Аналогично тем же комбинациям кодируются цифры и другие символы (точки, запятые, двоеточия и др.). Для передачи буквенного текста передается код буквы (00001) и затем — пятиразрядные комбинации кода текста; перед передачей цифр или других символов передается код цифры (00010).

На базе кода Бодо в различных странах разработаны телеграфные равномерные коды. Различие в кодах затрудняло международные телеграфные связи, поэтому в 1931 г. Международный консультативный комитет по телеграфии (МККТ) принял стандартный код МТК-1, близкий по виду к коду Бодо. Для стартстопных телеграфных аппаратов с клавиатурой пишущей машинки в 1932 г. был принят код МТК-2. В состав кода вошли 32 информационных и служебных символа. Он отличается от кода Бодо лучшей приспособленностью к пользованию клавиатурой пишущих машинок при передаче русского и латинского текстов. Этот код с незначительными изменениями применялся для обмена информацией в первых образцах ЭВМ.

Для передачи данных с использованием ЭВМ разработан ряд стандартных кодов, обеспечивающих кодовую совместимость ЭВМ. Структурной единицей при передаче данных принята восьмибитная комбинация — байт.

Так, в ЕС ЭВМ используются коды — КОИ-7, КОИ-8 (для обмена данными), КПК-12 — для перфокарт и ДКОИ — для внутренних операций в машинах.

Код КОИ-7 содержит 128 символов международного алфавитно-цифрового набора, включая математические и специальные символы. В этом коде символы кодируются таким образом. Кодовая комбинация состоит из двух частей: три старших разряда а7, а6 и а5 соответствуют адресу столбца, а четыре младших — а4 — а1 — адресу строки кодовой таблицы, в которой размещены кодируемые символы. Адрес, т. е. номера строк и столбцов, записывают в двоичном неизбыточном коде. Например, цифре 1 соответствуют комбинация 011 0001, символу % — 010 0101, букве К — 100 1011 и т. п. Код имеет три модификации, позволяющие иметь дополнительные управляющие символы (например, ВХ (000 1111) — обозначающий передачу латинских букв, ВЫХ (1000 1110) — русских букв). Восьмой бит используется как контрольный (для защиты от искажений по четности).

Код КОИ-8 объединяет все модификации КОИ-7. Для определения модификации используют дополнительный восьмой разряд.

Код для обработки информации ДКОИ содержит 256 кодовых комбинаций, включающих ряд функциональных, в том числе ряд комбинаций, предназначенных для кодирования тех или иных функций (16 столбцов и 16 строк, пронумерованных в шестнадцатеричной системе). Он разработан на основе международного кода EBCDIC (Exended Binary Decimal International Code) с добавлением букв русского алфавита. Например, кодовая комбинация 1110 0111 соответствует символу « = », кодовая комбинация 1111 0110 —символу « ? » и т. д.

Использование того ли иного кода определяется протоколом обмена данными, согласовываемым при разработке систем.

Комбинаторные коды. Такие коды основаны на применении математической теории соединений: перестановок (Рn), размещений () и сочетаний ().

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

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

.

Так, при n = 3 (например, а, б, в) и q = 2 возможны комбинации: аб, ав, ба, бв, ва, вб.

Коды по закону сочетаний представляют собой комбинации по q символов из n возможных, отличающиеся только символами. Число комбинаций

.

Так, при n = 4 (например, а, б, в и д) возможны сочетания: аб, ав, ад, бв, бд и вд. Такие коды называют кодами на одно сочетание (в каждой комбинации одинаковое число элементов). Если из заданного числа элементов составить комбинацию сочетаний по 1, по 2, ..., по n элементов, то общее число комбинаций ; такой код называют кодом на все сочетания. Код типа  при временном разделении элементов сигналов часто называют распределительным.

6.3 Помехозащищенные коды

Принципы построения помехозащищенных кодов. Простые числовые комплектные коды при числе символов m и числе элементов n0 позволяют образовать  комбинаций. Отсюда минимальная длина кодовой комбинации, необходимая для образования всех N0 комбинаций,

.

Коды, в которых используется совокупность всех комбинаций минимальной длины, называют минимальными или кодами безызбыточности. Их отдельные комбинации могут отличаться друг от друга всего в одном элементе. Искажение какого-либо одного элемента в результате воздействия помехи приводит к изменению передаваемой комбинации и, следовательно, к ошибке. Для оценки помехозащищенности пользуются кодовым расстоянием d — числом разрядов, в которых элементы одной кодовой комбинации отличаются от другой. Кодовое расстояние может быть определено сложением обеих комбинаций по модулю 2 (mod 2) так, как это показано в табл. 6.2 (сложение по mod 2 обозначают знаком ).

В сумме комбинаций будут нули в тех разрядах, где символы в обеих комбинациях одинаковы, а единицы — где символы различные. Расстояние между различными кодовыми комбинациями из заданного набора наглядно иллюстрируется матрицей кодовых расстояний. Пусть, например, дан некоторый произвольный набор комбинаций: 1) 1000; 2) 1100; 3) 0101; 4) 1111. Определим, например, кодовое расстояние между каждой парой комбинаций в некотором их произвольном наборе (табл. 6.3).

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

Существуют два основных подхода к формированию помехозащищенного кода: выбор из заданного набора (множества) безызбыточного кода комбинаций (слов) помехозащищенного кода с заданными свойствами; непосредственное преобразование k-значных комбинаций безызбыточного кода в (n > k)-значную комбинацию помехозащищенного кода с заданными свойствами.

 

                     Таблица 6.2                                                                       Таблица 6.3

x	y	xy		Номер кодовой комбинации	Кодовые расстояния между комбинациями
					1	2	3	4
0	0	0		1	0	1	3	3
1	0	1		2	–	0	2	2
0	1	1		3	–	–	0	2
1	1	0		4	–	–	–	0

В обоих случаях длина слов помехозащищенного кода оказывается большей, чем у безызбыточного кода с таким же набором комбинаций. Поэтому такие коды называют кодами с избыточностью. Пусть у безызбыточного кода длина кодового слова n0, тогда у избыточного кода она больше: n = n0 + n. При сравнении кодов избыточность оценивают коэффициентом избыточности R:

.

Коды с обнаружением и исправлением ошибок. Чтобы обнаружить ошибку, возникающую в одном символе, достаточно увеличить минимальное кодовое расстояние до dmin = 2. При этом декодирующее устройство будет реагировать только на заданный набор комбинаций, запрещая исполнение всех других, отличающихся от них по крайней мере на единицу. Для обнаружения одновременной ошибки в двух элементах кода кодовое расстояние должно быть увеличено до dmin = 3, в трех элементах до dmin = 4 и т. д. Таким образом, для обнаружения ошибок кратностью об нужно иметь минимальное кодовое расстояние dmin ≥ об + 1. При d > 2 можно не только обнаруживать, но и исправлять ошибки. Способность кода обнаруживать и исправлять ошибки определяется минимальным кодовым расстоянием d = и + об + 1, где и — число исправляемых ошибок (и ≤ об). Если исправляются все обнаруженные ошибки, то d = 2и + 1. Отсюда для исправления одиночной ошибки dmin = 3.

Среди помехоустойчивых кодов различают блочные и непрерывные.
К блочным относятся коды, с помощью которых сообщения передаются блоками из некоторого конечного числа символов. Из них равномерные коды имеют постоянное число символов в комбинации (например, код Бодо), неравномерные — различное (например, код Морзе). Непрерывные коды являются непрерывной последовательностью информационных и проверочных разрядов. Места этих разрядов определяются рекуррентными выражениями. Четкое разделение кодовых комбинаций отсутствует. Блочные коды могут быть разделимыми и неразделимыми. У разделимых кодов разряды четко делятся на информационные и проверочные, причем места проверочных разрядов в кодовой комбинации строго определены. У неразделимых, например у равновесного кода, такого деления нет.

Разделимые коды включают две группы: систематические и несистематические. К систематическим относятся коды, у которых сумма по модулю 2 двух разрешенных комбинаций является комбинацией того же кода. Их примером являются коды Хэминга и циклические коды. К несистематическим кодам относятся код, в котором проверочная комбинация является суммой единиц в информационной части, и код с проверкой на четность.

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

Например, возьмем в качестве исходного двоичный код с n = 3 (табл. 6.4). Пусть надо выбрать кодовые комбинации с dmin = 2 (тогда d = dmin — 1 = 1).

В качестве первой комбинации выбираем 001 (очередность выбора комбинации обозначена цифрой над ней: 0011 — первая).

В исходном коде вычеркиваем комбинации, расположенные в столбце ниже выбранной (000, 011 и 101). Выбираем следующую комбинацию 010 и дополнительно к уже вычеркнутым 000 и 011 исключаем комбинации 110 (вычеркнутые комбинации обозначены знаком *). Остаются не исключенными комбинации 100 и 111. Таким образом, выбранный набор 001, 010, 100, 111.

Нетрудно убедиться, что между оставшимися комбинациями dmln= 2. Аналогично можно построить код с dmln = 3, если учесть двойные ошибки, и с любым другим dmln.

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

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

Таблица 6.4

Комбинации ошибок	Искаженные комбинации при исходном коде
	000	0011	0102	011*	1003	101*	110*	1114
d = 1
001	001	000	011	010	101	100	111	110
010	010	011	000	001	110	111	100	101
100	100	101	110	111	000	001	010	011
d = 2
001	011	010	001	000	111	110	101	100
101	…	…	…	…	…	…
…	…	…	…	…

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

Комбинации с четным числом единиц	000	011	101	110
То же с нечетным числом единиц	001	010	100	111

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

Код может быть получен с помощью линейных математических преобразований (второй способ). Все элементы исходной кодовой комбинации по mod 2 суммируются. Если сумма равна 1, то для получения четных комбинаций к исходной добавляется еще единица; если же сумма равна 0, то добавляется 0 (для получения нечетных комбинаций делается наоборот). Пример такого кода приведен в табл. 6.5.

Таблица 6.5

Исходная комбинация	Сумма элементов по модулю 2	Полученная комбинация
111	111=1	1111
011	111=0	0110

Код имеет dmin = 2, он может обнаружить любое одиночное искажение, а также все искажения нечетной кратности.

Избыточность кода

.

Двоичный код на одно сочетание выполняется выбором из двоичного кода на все сочетания комбинаций с одинаковым числом единиц (l). Такой код также называют равновесным: . Например, код

1) 11000	3) 10010	5) 01100	7) 01001	9) 00101
2) 10100	4) 10001	6) 01010	8) 00110	10) 00011

Избыточность кода

.

Код обнаруживает любые одиночные искажения, а также многие двойные, тройные и другие искажения.

Коды с повторением предусматривают повторение каждой комбинации 2 раза или более. Такие коды могут быть в двух вариантах: повторение без инверсии и повторение с инверсией. Повторяться могут целые комбинации или отдельные элементы. Например, комбинация 01100 в таких кодах представляется таким образом:

Число элементов n и кодовое расстояние d увеличиваются пропорционально кратности повторения :

где  — минимальное кодовое расстояние в исходном коде.

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

6.4 Линейные коды

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

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

Групповые коды обозначают n, k, d, где n — общее число разрядов; k — число информационных разрядов; d — кодовое расстояние. Наиболее распространен способ задания таких кодов с помощью таблиц — «порождающих» или «базисных» матриц с числом строк k и рядов n. Например, для кода 7, 4, 3 «порождающие» матрицы G имеют вид:

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

Первые k рядов матрицы (al, a2, ..., ak) представляют собой информационную часть. При синтезе кода с различными n и k она может быть записана в так называемой канонической форме в виде единичной матрицы («1» по диагонали). Проверочная часть (контрольная подматрица Ь1, Ь2, ..., bn - k) формируется различными способами со следующими ограничениями: каждая строка контрольной подматрицы содержит не менее d — 1 единиц; строки контрольной подматрицы отличаются не менее чем в d — 2 позициях; сумма любых d — 1 строк не равна нулю.

Таким образом, для каждого n, k, d кода может быть получено то или иное число вариантов. Все варианты эквивалентны по вероятности правильного приема, но могут иметь различные по степени сложности кодирующие и декодирующие устройства.

Правильность принятого кода определяется z = n — k проверками, которые сводятся к контролю четности суммированием по модулю 2 соответствующих проверочных и информационных символов. В результате проверок получают двоичное число Sl, S2, ..., Sn-k, называемое проверочным вектором, или синдромом. Здесь Sl — результат первой проверки; S2 — второй; Sn-k — результат z-й проверки. Если синдром равен нулю, то это свидетельствует об отсутствии ошибки, а если не равен нулю, — то ошибка есть. По виду синдрома ошибка может быть только обнаружена или обнаружена и исправлена.

Один из методов обнаружения ошибки рассмотрим на примере кода Хэминга (n, k, d = 3), сущность которого в том, что в результате z проверок получают двоичное число, которое при переводе в десятичное говорит о номере позиции, в которой произошла ошибка. Для этого синдром Sz, Sz-1, ..., S2, S1 должен иметь число двоичных разрядов z, соответствующее десятичному числу n — 1 (от 0 до n-й позиции кода). Следовательно, при z проверочных разрядах:

; (6.1)

. (6.2)

Знак « > » в выражении (6.1) говорит о том, что z округляется до целого числа в большую сторону. Из выражений (6.1) и (6.2) следует, что максимальное число информационных разрядов k при заданном n будет в случае, если n + 1 = 2с, где с — целое число.

Число информационных символов для N сообщений определяется из условия k ≥ log2 N. Зная k и соотношение между z и n, можно определить число контрольных символов:

k……	0	1	2	3	4	5	6	7	8	9	10	11
z……	1	2	3	3	4	4	4	4	4	4	4	4
n……	1	3	5	6	7	9	10	11	12	13	14	15

Контрольными символами, формируемыми кодирующим устройством, дополняют соответствующие последовательности символов до четного числа единиц с таким расчетом, чтобы при безошибочном приеме Sl, S2, ..., Sz равнялись нулю. Для упрощения кодирующего устройства в качестве контрольных символов удобнее выбрать такие, которые встречаются в последовательностях Sl, S2, ..., Sz только один раз. При этом символ проверочного разряда может быть найден в результате решения только одного уравнения. Как видим, в выражения (6.3) — (6.6) для Si один раз входят те разряды, номер которых равняется 2с. Именно их (a1, a2, a4, а8) и выбирают в качестве контрольных, приняв в них Sl, S2, ... = 0; найдем значения контрольных символов:

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

а1	а2	а3	а4	а5	а6	а7	.
0	1	0	1	0	1	0

Проверочные позиции (контрольные символы): а1 = 0, при приеме кодовой комбинации осуществляют z проверок. Первая проверка должна дать S1 — младший разряд синдрома. Если S1 = 1, то это значит, что ошибка произошла в одном из символов, находящемся на позициях 1, 3, 5, 7, ..., т. е. на позициях, номер которых имеет в двоичной системе единицу в младшем разряде. Таким образом

. (6.3)

Второй проверке подвергаются разряды, номер которых в двоичной системе имеет единицу во втором разряде:

. (6.4)

Аналогично

. (6.5)

. (6.6)

а2 = 1, а4 = 1. Допустим, что в результате искажения на приемной стороне принята комбинация 0101110 (искажение на пятой позиции). Тогда

.

Полученный синдром S3S2S1 → 101 (пять в десятичной системе, и следовательно, ошибочно принят пятый элемент комбинации а5). Исправив его (с 1 на 0), окончательно получим 0101010.

Пусть искажение произошло в проверочном разряде, например, в а4. Тогда будет принята комбинация 010010. При этом S1 = 0; S2 = 0; S3 = 1, т. е. S3S2S1 → 100, а значит, искажен символ а4. Коррекция в этом случае не нужна, так как комбинация исходного кода принята правильно.

Циклические коды — это линейные коды, у которых любая кодовая комбинация anan-1an-2...a2a1 при циклическом сдвиге дает кодовую комбинацию an-1an-2...a2a1an, принадлежащую тому же коду.

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

Для получения циклического кода сначала выбирают безызбыточный двоичный код, число разрядов k в комбинациях которого обеспечивает передачу заданного объема сообщений (2k). Этому коду соответствует полином G(х) степени (k — 1). Например, кодовая комбинация 1111 отображается полиномом G(х) = х3 + х2 + х + 1. При этом полный объем сообщений будет содержать 24 = 16 кодовых комбинаций (включая комбинацию 0000).

Длина комбинации помехозащищенного кода должна содержать большее число разрядов n = k + r, где r — число проверочных символов.

Известны различные способы формирования циклических кодов. Рассмотрим один из них, при котором в сформированных комбинациях коэффициенты при высших степенях полинома (от n до n — k) соответствуют информационным разрядам, а при низших (n — k — 1 и ниже) — проверочным.

Чтобы получить полином, соответствующий n-разрядному коду, исходный G(х) умножают на хr.

Для дальнейших операций с кодом с целью обеспечения его защиты от помех используют так называемый «порождающий» полином. Его находят разложением на множители двучлена хn — 1 = P1(x) · P2(x) · ... · Рi (х).

В качестве порождающего полинома выбирают сомножитель РS(х), имеющий степень r ≤ n — k. При таком полиноме для формирования кодовых комбинаций циклический код при r ≥ 2 будет обнаруживать все одиночные и двойные ошибки, а также все групповые ошибки с числом искаженных символов r и менее. Порождающий полином вида PS(x) = 1 + х позволяет обнаружить все одиночные и любое число нечетных ошибок.

Из всех ошибок длиной r + 1 разрядов не обнаруживается 1/2r–1 часть, а при длине большей, чем r + 1, 1/2r часть.

Для получения помехозащищенной кодовой комбинации F(х) произведение G(х)хr делят на PS(x). Остаток от деления R(х) суммируют с произведением G(х)хr: F(х) = G(х)хr + R(х). Полученная комбинация делится на полином PS(x) без остатка.

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

Рассмотрим пример формирования помехозащищенного кода на основе безызбыточного четырехразрядного кода. Пусть исходная комбинация отображается полиномом G(х) = х3 + х2 + х + 1, число проверочных символов     r = 3.

Умножив G(х) на х3, получим (х3 + x2 + х + 1) х3 = х6 + х5 + х4 + х3 → 1111000. Первые четыре символа представляют собой исходную комбинацию, а три последних предназначены для контрольных символов. Для выбора порождающего полинома разложим двучлен хn — 1 = х6 — 1 на сомножители  х6 — 1 = (х3 + 1)·(х3 — 1). В качестве порождающего полинома выберем            х3 + 1 ↔ 1001. Разделив полином х6 + х5 + + х4 + х3 на х3 + 1, найдем, что остаток от деления R(х) = х2 + х. Тогда кодовая комбинация для передачи по линии связи примет вид:

.

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

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

6.5 Методы повышения достоверности передачи кодированной                                                            информации

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

В качестве примера рассмотрим некоторые виды сигнальных кодов (иногда называемых в литературе «линейными», т. е. предназначенными для передачи по линии). Исходный код, обычно называемый NRZ (non return to zero), применяемый в униполярной форме (в виде импульсов тока одного знака), является непомехозащищенным. Лучшими свойствами (при той же энергии сигнала) обладает биполярный код NRZ, где символ 1 передается импульсом положительной, а символ 0 импульсом отрицательной полярности (рис. 6.1, б). Избыточность достигается за счет наличия двух уровней сигнала различной полярности (+U и – U). Код «Манчестер 11» (рис. 6,1, в) является биполярной сигнальной формой упоминавшегося ранее кода, в котором символ 1 преобразуется в комбинацию 10, а символ 0 — в комбинацию 01. При этом, как и в биполярном коде NRZ, символ передается импульсом положительной, а символ 0 — импульсом отрицательной полярности. Здесь вносится дополнительная избыточность за счет уменьшения скорости передачи информации. Ошибка может быть обнаружена при посимвольном приеме. Ее критерием является заданное превышение продолжительности действия какого-либо из уровней сигнала над временем передачи одного сигнального бита. Положительным свойством кода является несложность обеспечения ввода в синхронизм системы передачи.

В сигнальном коде AMI (alternate mark inversion) (рис. 6.1, г) избыточность вносится с помощью использования (в простейшем случае) трех

 

Рис. 6.1. Примеры кодов последовательного интерфейса ЭВМ

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

При использовании простейшего кода AMI возникает сложность в обеспечении ввода системы передачи в синхронизм при передаче длинных последовательностей нулевых символов. В связи с этим более широко распространены его формы, называемые BNZS, где цепочки из N нулей заменяют подстановками знакопеременных символов. Так, в коде BNZS цепочки из трех последовательных нулей заменяют подстановкой BOV или OOV (рис. 6.1, д), где В, V соответственно импульсы, кодируемые по правилам кода AMI и с нарушением этих правил. При выборе вида подстановки необходимо, чтобы число импульсов В между двумя последовательно расположенными импульсами V было нечетным и чередовалась полярность импульсов V. Существуют и другие формы сигнальных кодов.

Внесение асимметрии в канал передачи и применение пошаговой синхронизации. Повышение помехозащищенности при передаче кодовых комбинаций по линии связи может быть достигнуто применением пошаговой синхронизации и широтно-импульсной модуляции с контролем длительности импульсов. Пошаговая синхронизация позволяет обеспечить четкость синхронной работы передающего и приемного устройства и числовой защиты. Различие в длительности передачи символов 1 и 0 позволяет свести к нулю трансформацию вида 1 → 0 и обеспечить dmin = 2 даже при передаче исходного безызбыточного кода. Наличие числовой защиты контроля длительности импульсов и пошаговой синхронизации существенно сокращает возможность приема ложных комбинаций при групповых ошибках.

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

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

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

167

1. Группы интересов и политика
2. Производство фиточая
3. Американские депозитные расписки и возможности их выпуск Российскими эмитентам
4.  Федеральные государственные требования ФГТ к структуре основной общеобразовательной программы дошкольн
5. ТЕМА МОТИВІВ У ХУДОЖНІЙ ПРОЗІ АНДРІЯ ПЛАТОНОВА 10
6. записка Індивідуальне самостійне завдання є видом позааудиторної роботи курсанта яке виконується в п
7. Система психологопедагогической работы по приобщению детей к культуре самоорганизации
8. Тема- Дизайн проект путеводителя по городу Тольятти студент .
9. либо другой В этой книге нет ни слова правды и всё же ~ ни слова лжи
10. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата мистецтвознавства Харк
11. Лабораторная работа ’2 Лабораторная работа ’4 Проверка уровня сформированности основных.html
12. ПРАКТИКУМ. СОЗДАНИЕ ФУНКЦИОНАЛЬНОЙ МОДЕЛИ С ПОМОЩЬЮ BPWIN 4
13. Лекция 2 Рыночный механизм и его элементы- спрос предложение равновесная цена Рыночный спрос
14. реферат дисертації на здобуття наукового ступеня доктора медичних наук Киї.
15. на тему- Организация самостоятельной работы ученика в современных условиях
16. Контрольная работа- Мультисписки
17. Основные формы и системы оплаты труда
18. 5Пятерочка место прохождения практики Выполнил- Студент 2 курса заочного отделения Гр
19. реферат дисертації на здобуття наукового ступеня кандидата економічних наук Дніпропе.
20. Образ Петербурга в классической литературе XIX века

Материалы собраны группой SamZan и находятся в свободном доступе