Разработка декодера инверсного кода

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

1) прием сигнала сводится не к измерению, а к обнаружению 1 или 0;

2) сообщения в цифровой форме легко обрабатываются, запоминаются, коммутируются и регистрируются;

3) возможна многократная передача без накопления ошибок;

4) применение помехоустойчивого кодирования позволяет значительно увеличить достоверность передачи телемеханических сообщений;

5) упрощаются требования, предъявляемые к радиолиниям в отношении калибровки эталонных уровней;

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

Под кодированием в широком смысле понимается переход от одного способа задания информации к другому, допускающий восстановление исходной информации. Теория кодирования получила большое развитие, начиная с 40-х годов ХХ века после работ К. Шеннона.

В связи с появлением кодирования с исправлением ошибок возникает необходимость создания соответствующих декодеров.

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

1. Исследовательская часть

1.1 Кодирование

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

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

Кодовая последовательность (комбинация) — представление дискретного сигнала.

Целями кодирования сообщений обычно являются:

1) передача по общему каналу связи нескольких или многих сообщений для кодового разделения сигналов;

2) повышение помехоустойчивости и достоверности передачи сообщений;

3) более экономное использование полосы частот канала связи, т. е. уменьшение избыточности;

4) уменьшение стоимости передачи и хранения сообщений;

5) обеспечение скрытности передачи и хранения информации;

6) преобразование любой информации независимо от ее происхождения и назначения в единую систему символов;

7) приведение исходных символов в соответствие с характеристиками канала связи.

Любая кодовая комбинация содержит определенный набор элементов или символов (1 и 0, а и б), которые называются буквами алфавита, а весь набор букв образует алфавит кода. Для двоичного кода алфавит состоит из двух символов, для троичного их число увеличивается до трех (а, б, в или 1, 2, 3), а в десятичном оно равно десяти. Таким образом, основание кода Х — это количество признаков или число букв (цифр). Кодовая комбинация, составленная из n символов или n элементов, называется кодовым словом (кодовым блоком), имеющим длину n или число разрядов n. Если длина всех кодовых комбинаций одинакова, то такие коды называют равномерными (комплектными). Например, код 001, 011, 101 является комплектным, а код 1, 11, 101 — некомплектным. В телемеханике обычно используют только равномерные коды.

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

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

На рис. 1 показано кодовое дерево для двоичного трехразрядного кода.

Рис. 1. Графическое представление кодового дерева

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

Рис. 2. Классификация двоичных кодов

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

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

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

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

Основные характеристики двоичных кодов. Двоичные коды характеризуются весом кода w, кодовым расстоянием d и весовой характеристикой F (w). Весом кода w называется количество единиц в кодовой комбинации. Например, для кодовой комбинации 1 011 110 вес кода w = 5.

Число одноименных разрядов двух кодовых комбинаций, в которых значения символов не совпадают, есть кодовое расстояние d между этими комбинациями. Для определения кодового расстояния необходимо сложить эти комбинации по модулю 2. Например, для кодовых комбинаций 10 101 и 110 d=3, так как 10 101 A00110 = 10 011 (w=3). Таким образом, кодовое расстояние определенного кода — это минимальное число элементов, которыми любая кодовая комбинация отличается от другой (по всем парам кодовых слов). Например, для кода, состоящего из комбинаций 1100, 1000, 1011, 1101, dmin=1, так как 1100 A1101=0001. (w=1).

Весовая характеристика кода F (w) — число кодовых комбинаций определенного веса w. Например, для кода, представленного комбинациями 1 (w = 1), 11 010 (w = 3), 10 110 (w = 3), 11 110 (w = 4), имеем F (1) = 1, F (3) = 2, F (4) = 1, т. е. код состоит из одного кодового слова веса 1, двух слов веса 3 и одного слова веса 4.

Корректирующие коды имеют и некоторые дополнительные характеристики.

Абсолютная избыточность кода определяется числом проверочных символов ®, т. е. количеством разрядов, отводимых для коррекции ошибок.

Относительная избыточность кода ® есть отношение числа проверочных символов к длине кода: R = r n. В общем случае относительную избыточность рассчитывают по формуле R = I — log2 N p log2 N, где N p — число кодовых комбинаций, используемых для передачи сообщений (рабочая мощность кода); N — полное число кодовых комбинаций (мощность кода).

1.2 Корректирующие коды

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

Отсюда и деление кодов на две большие группы: 1) коды с обнаружением ошибок; 2) коды с обнаружением и исправлением ошибок.

Принципы обнаружения и исправления ошибок кодами проиллюстрированы с помощью геометрической модели трехразрядного двоичного кода (рис. 3.). Если использовать все восемь кодовых комбинаций, записанных в вершинах куба, то образуется двоичный код на все сочетания. Такой код является непомехоустойчивым. Если же уменьшить число используемых комбинаций с восьми до четырех, то появиться возможность обнаружения одиночных ошибок. Для этого выбираются только такие комбинации, которые отстоят друг от друга на расстояние d=2, например, 000, 110, 011 и 101. Остальные кодовые комбинации не используются. Если будет принята комбинация 100, то очевидно, что при ее приеме произошла одиночная ошибка. Представленные комбинации построены по определенному правилу, а именно содержат четное число единиц, а принятая комбинация 100 — нечетное.

Рис. 3. Геометрическая модель трёхразрядного двоичного кода

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

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

1.3 Инверсный код

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

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

Таблица 1

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

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

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

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

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

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

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

Кодовое расстояние инверсного кода равно количеству разрядов исходного кода при k<4 и равно 4 при k ?4. Например, при d=4 код может обнаруживать двойные ошибки и исправлять одиночные. Обычно этот код используется только для обнаружения ошибок. Он позволяет обнаруживать ошибки любой кратности за исключением таких, когда искажены 2 информационных символа и соответствующие им 2 контрольных, 4 информационных и соответствующие им 4 контрольных и т. д.

Коэффициент избыточности инверсного кода равен 0,5.

2. Конструкторская часть

2.1 Структурная схема

Разрабатываемый декодер инверсного кода состоит из следующих блоков:

1. Блок хранения данных.

2. Блок подсчета количества единиц.

3. Блок определения ошибки.

4. Блок исправления ошибки.

Рис. 4. Структурная схема декодера инверсного кода

2.2 Описание работы схемы

Блок хранения данных

Блок хранения данных спроектирован на микросхемах К555ИР8.

Принципиальная электрическая схема блока изображена на рис. 5.

Рис. 5. Принципиальная электрическая схема блока хранения данных

Блок хранения данных состоит из двух сдвиговых регистров К555ИР8.

Принятая кодовая комбинация поступает в систему через контакт А1 разъёма ГРПМШ-1. Кодовая комбинация поступает в последовательном коде.

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

Полученная комбинация подаётся на информационные коды первого регистра (DD1). Далее с помощью тактового генератора происходит сдвиг записанной информации в регистр на 1 бит. НА освободившееся место в регистре записывается следующий бит полученной комбинации.

Так как длина кодовой комбинации равна 16 разрядам, а разрядность одного регистра 8 бит, то были взяты 2 регистра. Выходная ножка 13 первого регистра (DD1) подаётся на информационные входы второго регистра (DD2). Таким образом в первом регистре хранятся младшие 8 битов принятой комбинации, а во втором — старшие8 бита.

Записанная в регистры информация в дальнейшем используется для определения наличия ошибок и их исправления.

Блок подсчета количества единиц

Блок подсчета количества единиц спроектирован на микросхеме К155ИП2.

Принципиальная электрическая схема блока представлена на рисунке 6.

Рис. 6. Принципиальная электрическая схема блока подсчета единиц

Схемой контроля четности анализируются информационные разряды кодовой комбинации. Если число единиц четное, то с выхода РЕ снимается единица. Если число единиц в кодовой комбинации нечетное, то единица снимается с выхода Р0.

Полученный алгоритм представлен на рисунке 7.

Рис. 7. Алгоритм определения количества единиц Блок определения ошибки Блок определения ошибок спроектирован на микросхемах К555ЛН1, К555ЛИ1, К555ЛЛ1.

Принципиальная электрическая схема блока представлена на рисунке 8.

Если число единиц в кодовой комбинации четное, то с выхода РЕ схемы контроля четности снимается единица, которая открывает верхние схемы 2И элементов DD6, DD7. Тем самым ко входу сумматоров DD14, DD15 поступают контрольные символы в прямом виде.

Если число единиц в кодовой комбинации нечетное, то с выхода Р0 схемы контроля четности снимается единица, которая открывает нижнии схемы 2И элементов DD6, DD7. Тем самым ко входу сумматоров DD14, DD15 поступят контрольные символы в инверсном виде с выходов элементов НЕ DD3, DD4.1.DD4.2.

Полученный алгоритм представлен на рисунке 9.

Рис. 8. Принципиальная электрическая схема блока определения ошибки Рис. 9. Алгоритм определения наличия ошибок

Блок исправления ошибки Блок определения ошибки спроектирован на микросхемах К555ЛП5.

Блок исправления ошибки и формирования результата представлен на рисунке 10.

Рис. 10. Принципиальная электрическая схема блока исправления ошибки и формирования результата При отсутствии ошибки на выходах всех сумматоров будут нули. И с помощью элементов DD16, DD17 на выходе будет правильная комбинация. В случае если в кодовой комбинации будут ошибки, то на выходе сумматоров DD14, DD15 появятся единицы. Количество единиц соответствует количеству ошибок. Если ошибка единичная, то она исправится схемами суммы по модулю 2 DD16, DD17. И на выходе сформируется правильная комбинация.

Алгоритм представлен на рисунке 11.

Рис. 11. Алгоритм функционирования блока исправления ошибки формирования результата.

Заключение

В результате проделанной работы спроектирован декодер инверсного кода. Так же были разработаны:

1. Разработаны электрические схемы: электрическая, принципиальная;

2. Разработан алгоритм функционирования декодера

3. Получены практические навыки разработки конкретных устройств.

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

С помощью него возможно определение любого количества ошибок. И исправление единичной ошибки.

1. Добрушин Р. Л., Самойленко С. И. Коды, исправляющие ошибки.-М.: Мир, 1986, 590 с., ил.

2. Пухальский Г. И., Новосельцева Т. Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. — М.: Радио и связь, 1990.

3. Сирока Н. И., Кривинченко Г. А. Конспект лекций для студентов специальности «Автоматическое управление в технических системах». Минск. 2001.

4. Темников Ф. Е., Афонин В. А., Дмитриев В. И. Теоритические основы информационной техники. — 2-е изд., перераб. и доп.-М.:Энергия, 1979.-512 с.

кодирование микросхема декодер инверсный