Разработка программы кодирования по алгоритму Хемминга

Министерство образования и науки Российской Федерации

Федеральное Государственное Бюджетное Образовательное Учреждение Высшего Профессионального Образования

«Комсомольский-на-Амуре государственный технический университет»

Факультет Инженерно-экономический

Кафедра Промышленная электроника

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовой работе

по дисциплине “Электронные промышленные устройства”

по теме “Разработка программы кодирования по алгоритму Хемминга”

Студент Т. Ю. Барышева

Руководитель Е. П. Иванкова

Содержание

Введение

. Принципы построения корректирующего кода Хемминга

. Блок-схема программы

. Текст программы на языке Ассемблер

. Примеры моделирования в Proteus для исходных сообщений

Заключение

Список использованных источников

Введение

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

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

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

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

1. Принципы построения корректирующего кода Хемминга

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

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

.( 1 )

Единица во втором разряде контрольного числа свидетельствует о наличии ошибки на одной из позиций, двоичные номера которых имеют единицу во втором разряде. Такими позициями являются 2, 3, 6, 7, 10, 11 и т. д. Символы с перечисленными номерами войдут во вторую проверку:

.( 2 )

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

.( 3 )

Для последней проверки с номером  легко получить, что:

 ;( 4 )

код хемминг моделирование массив

где .

Поскольку контрольные символы должны обеспечивать четность проверочных сумм, они включаются лишь в одну проверку. Только в одну проверку входят символы, двоичные номера позиций которых являются целыми степенями двойки, т. е. 1, 2, 4, 8, 16 и т. д. На этих позициях и размещаются контрольные символы. Значения контрольных символов находятся как результат суммирования всех символов, входящих в данную проверку. Из выражений (1) - (4) можно определить значения контрольных символов:

 ;

 ;

 ;( 5 )

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

.( 6 )

что обеспечивает четность последней проверки.

При декодировании вначале производится  проверок на четность в соответствии с выражениями (1) - (4). Затем производится  проверка. При этом возможен случай, когда все проверки дают нулевой результат. Это соответствует отсутствию ошибки. Если некоторые из проверок и  проверка дают результат, отличный от нуля, то это свидетельствует об однократной ошибке. Номер искаженной позиции указывает контрольное число. При наличии двукратной ошибки некоторые из  проверок дадут результат, отличный от нуля, а последняя проверка даст нуль.

Рассмотрим построение кодирующего и декодирующего устройств семиразрядного кода Хэмминга. Из семи символов кода три являются контрольными, а остальные - информационными. Согласно правилу построения кода, информационные символы должны располагаться на позициях 3, 5, 6, 7, а контрольные - на позициях 1, 2, 4. Расположение контрольных символов в начале кодовой комбинации создает определенные неудобства при построении кодирующих устройств (необходимо иметь буферный накопитель с числом разрядов, равным длине кодовой комбинации) и приводит к задержке в передаче информации, поскольку для определения значений контрольных символов необходимо сформировать суммы вида (5), в которые входят значения последующих информационных символов. Устранить отмеченные недостатки можно за счет некоторой модификации кода Хэмминга путем перестановки контрольных символов в конец кодовой комбинации, а информационных символов в ее начало. При этом корректирующие свойства кода сохраняются. В результате, контрольные символы займут позиции 5, 6, 7, а информационные - позиции 1 - 4. Проверочные суммы составятся по следующему правилу):

 ;

 ;

 .(7)

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

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

Рисунок 1 - Схемы кодирующего (а) и декодирующего (б) устройств кода Хемминга

Выходы схем  связаны со входами счетных триггеров , предварительно устанавливаемых в исходное нулевое состояние импульсами . В зависимости от числа импульсов, поступивших на входы счетных триггеров в течение первых четырех тактов, к моменту поступления пятого тактового импульса они перейдут в состояние  (при нечетном числе единиц) или в состояние  (при четном числе единиц). Состояния триггеров  определяют значения контрольных символов, размещаемых соответственно на позициях 5, 6, 7. Формирование импульсов, отображающих контрольные символы (единица - импульс, нуль - пауза), производится с помощью  пятого, шестого и седьмого тактов, подаваемых на входы схем , связанных с выходами триггеров . Полная кодовая комбинация корректирующего кода образуется на выходе семивходовой схемы , входы которой связаны с выходами схем . Формирование комбинации осуществляется последовательно во времени в течение семи тактов. После прихода седьмого тактового импульса все триггеры схемы переводятся в исходное нулевое состояние. Таким образом, за один цикл, состоящий из семи тактов, обеспечивается формирование трех контрольных символов и передача в канал связи семиразрядной кодовой комбинации корректирующего кода. При декодировании принятой информации устройством (рисунок 1,б) выполняются следующие операции: занесение информационных символов в регистр, контроль принятой информации и обнаружение ошибок, выдача информации с исправлением обнаруженных ошибок. В процессе приема кодовых комбинаций происходит потактное занесение информационных символов в регистр, выполненный на триггерах , где происходит их запоминание. Занесение осуществляется последовательно во времени тактовыми импульсами  через логические схемы . Запоминание контрольных символов не производится. Одновременно импульсы, проходящие через схемы  в тактах, соответствующих передаче единиц кода, поступают на входы логических схем  в сочетаниях, определяемых алгоритмом проверки, заданным соотношениями (7). Выходы схем  связаны с входами счетных триггеров , которые определяют четность или нечетность соответственно первой, второй и третьей проверки. Состояния триггеров после поступления седьмого  определят значения разрядов контрольного числа. При отсутствии искажений триггеры  будут находиться в состоянии  Если кодовая комбинация принята с ошибкой, один или несколько триггеров после семи тактов окажутся в положении . Поскольку при кодировании были изменены позиции проверочных символов, изменились и контрольные числа, соответствующие позициям искаженных символов. При искажении первого символа будет получено контрольное число 011, второго - 101, третьего -110, четвертого - 111, пятого - 001, шестого - 010, седьмого - 100. В приведенной схеме исправление одиночных ошибок производится только в информационных разрядах кода.

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

Корректирующий код Хемминга имеет следующее представление (таблица 1):

Таблица 1 - Представление кода Хемминга

Согласно выражений (5) контрольные биты определяются по формулам:

 ;

 ;( 8 )

 .

Для большей наглядности перепишем выражения (8) в привязке к информационным и контрольным битам:

,

,( 9 )

.

Поскольку в исходных данных сообщения имеют вид  (таблица 2), то для формирования кода Хемминга потребуется перенос информационных бит в другие разряды.

Таблица 2 - Представление исходных данных

Бит  необходимо перенести из восьмой позиции в третью, бит  необходимо перенести из седьмой позиции в пятую, бит  необходимо перенести из пятой позиции в седьмую.

Таким образом, необходимо выполнить следующее преобразование:

Произведем разработку программы формирования кода Хемминга в соответствии с перечисленными преобразованиями.

. Блок-схема программы

3. Текст программы на языке Ассемблер

.include"m128def.inc"

.cseg ; директива .cseg определяет начало сегмента кода

.org 0946 ; директива .org устанавливает указанный адрес в счетчик командR23,0xFFDDRB,R23 ;инициализация порта B на выводR23,0x00DDRA,R23 ;инициализация порта А на ввод:R23,PINA ;запись в регистр R23 исходного сообщения с порта А0x0944,R23;запись исходного сообщения в ячейку ОЗУR16,R23 ;запись исходного сообщения в регистр R16R16,0x80 ;выделение первого информационного битаR17,R23 ;запись исходного сообщения в регистр R17R17,0x40 ;выделение второго информационного битаR17 ;сдвиг влево второго информационного бита в старший разрядR18,R23 ;запись исходного сообщения в регистр R18R18,0x20 ;выделение третьего информационного битаR18R18 ;сдвиг влево третьего информационного бита в старший разрядR19,R23 ;запись исходного сообщения в регистр R19R19,0x10 ;выделение четвёртого информационного битаR19R19R19 ;сдвиг влево четвёртого информационного бита в старший разрядR20,R16 ;запись первого информационного бита в регистр R20R20,R17R20,R19 ;вычисление первого контрольного битаR21,R16 ;запись первого информационного бита в регистр R21R21,R18R21,R19 ;вычисление второго контрольного битаR22,R17 ;запись второго информационного бита в регистр R22R22,R18R22,R19 ;вычисление третьего контрольного бита

LSR R22R22R22

LSR R22 ;сдвиг вправо третьего контрольного бита в третий разряд

LSR R21R21R21

LSR R21R21R21 ;сдвиг вправо второго контрольного бита в первый разряд

LSR R20R20R20R20R20R20

LSR R20 ;сдвиг вправо первого контрольного бита в нулевой разрядR19 ;сдвиг вправо четвёртого информационного бита в шестой разрядR18R18 ;сдвиг вправо третьего информационного бита в пятый разрядR17R17R17 ;сдвиг вправо второго информационного бита в четвертый разряд

LSR R16R16R16 R16R16 ;сдвиг вправо первого информационного бита во второй разрядR23,R16 ;запись первого информационного бита в регистр R23

OR R23,R17R23,R18R23,R19

OR R23,R20R23,R21R23,R22 ;формирование кода Хемминга (объединение информационных и контрольных битов)0x0945,R23;запись кода Хемминга в ячейку ОЗУPORTB,R23 ;вывод кода Хемминга в порт BM ;возврат на опрос порта А

. Примеры моделирования в Proteus для исходных сообщений

Сформируем код Хемминга для исходных данных:

1) для исходного сообщения  получим:

формирование контрольных бит:

,

,

.

Добавив контрольные биты, получим код Хемминга:

Таким образом, для сообщения  сформирован код Хемминга

Произведем проверку расчетов с результатами вычислений в интегрированной среде Proteus на базе микроконтроллера ATmega128 (рисунок 2).

Рисунок 2 - Преобразование исходного сообщения  в код Хемминга

Проверка дала аналогичные результаты.

2) для исходного сообщения  получим:

перенос информационных бит в необходимые позиции:

формирование контрольных бит:

,

,

.

Добавив контрольные биты, получим код Хемминга:

Таким образом, для сообщения  сформирован код Хемминга

Произведем проверку расчетов с результатами вычислений в интегрированной среде Proteus на базе микроконтроллера ATmega128 (рисунок 3).

Рисунок 3 - Преобразование исходного сообщения  в код Хемминга

Проверка дала аналогичные результаты.

Заключение

В результате выполнения курсовой работы были изучены принципы построения корректирующего кода Хемминга, разработана программа преобразования исходных сообщений с помощью кода Хемминга на языке Ассемблер, выполнено моделирование выполнения кода на базе микроконтроллера ATmega128 с помощью программы Proteus.

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

Код Хэмминга используется в некоторых прикладных программах в области хранения данных, особенно в RAID2, кроме того, метод Хэмминга давно применяется в памяти типа ECC позволяет «на лету» исправлять однократные и обнаруживать двукратные ошибки.

Список использованных источников

1.      Абакумов, В. Г. Электронные промышленные устройства / В. Г. Абакумов. - К. : Вiща школа, 1978. - 376 с.

.        Блейхут Р. Теория и практика кодов, контролирующих ошибки / Р. Блейхут. - пер. с англ. - М. : Мир, 1986, 576 с.

.        Питерсон У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон. - пер. с англ. - М. : Мир, 1976, 600 c.

.        Лановенко В. В. Электронные промышленные устройства / В. В. Лановенко. - Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2006.-87 с.