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

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

Федеральное государственное бюджетное образовательное

 учреждение  высшего профессионального образования

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

 технический  университет» 
 
 

       Факультет электротехнический

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе 

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

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

   Студент группы 7ПЭ-1                                                             Д.В. Ожерельев

                                                                   подпись, дата

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

                                                                   подпись, дата

   Нормоконтролёр                                                                      Е.П. Иванкова

                                                                   подпись, дата 
 
 
 
 
 
 

   2011

       

       Содержание 

   Введение.................................................................................................................4     

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

2 Описание алгоритма работы программы. Блок схема....................................6

3 Текст программы с распределением ячеек памяти, мнемокодами, машинными кодами и комментариями................................................................7

4 Примеры моделирования в Proteus...................................................................9

5 Контрольные примеры для исходных сообщений.........................................10

   Заключение...........................................................................................................11

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

      В середине 1940-х годов Ричард Хэмминг работал в знаменитых Лабораториях Белла на счётной машине «Bell Model V». Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машину с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую подпрограмму.

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

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

   1) К исходной комбинации информационных символов добавляются контрольные символы количество которых вычисляется по формуле (1).

                                

где  – число контрольных символов;

       – число информационных символов.

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

   2) Формируется результирующая комбинация и передаётся в линию связи.

   3) На приёмной стороне производятся проверки. Каждая проверка представляет собой сумму по модулю 2 определённого количества символов кода: 

   4) Из результатов проверок составляется  слово: 

   Это слово в двоичной форме представляет собой номер искаженной позиции. 

Таблица 1 – Проверки для  ,

          001           010          011           100           101          110          111 

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

   Каждый  контрольный символ равен сумме  по модулю 2 информационных, входящих в ту же проверку: 
 
 

   Код Хемминга позволяет исправить однократную  ошибку. Двукратная ошибка не обнаруживается и не исправляется. 
 
 
 
 
 
 
 
 

    Исходное информационное слово помещается в ячейку памяти с адресом 0993. Затем путем циклических сдвигов влево, вправо, получаем отдельные биты информационного слова в виде . Затем вычисляем контрольные символы с помощью формул (3,4,5). Контрольные символы также будут получены в виде слова .

       Следующий шаг программы –  расстановка полученных символов  в соответствующие им позиции  кода Хемминга с помощью циклических сдвигов влево, вправо и логической операции «ИЛИ».

   Результат помещается в ячейку памяти по адресу 0994. Блок схема программы кодирования приведена на рисунке 1. 

 

 

 

 

 

 

 

 
 

Рисунок 1 – Блок-схема программы кодирования  
 
 
 
 
 
 
 
 

    Текст разработанной программы  с распределением ячеек памяти, мнемониками, машинными кодами и комментариями. 

.include"m128def.inc"

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

                      

.org 0       ; директива .org устанавливает PC=0893 и следующая команда будет располагаться во flash-памяти по этому адресу

      LDI R16,0xFF

      OUT DDRB,R16  ;инициализация порта B на вывод 

      LDI R17,0x00

      OUT DDRA,R17  ;иницилизация порта А на ввод

S:

      IN R18,PINA   ;запись в регистр  R18 исходного сообщения с порта А

      STS 0x0993,R18;запись исходного сообщения  в ячейку ОЗУ 0993h

      LDS R19,0x0993;запись в регистр R19 исходного  сообщения

      ANDI R19,0x01 ;выделение первого информационного бита

      MOV R20,R19   ;запись первого информационного бита в регистр R20

      LDS R19,0x0993;запись в регистр R19 исходного  сообщения

      ANDI R19,0x02 ;выделение второго информационного бита

      MOV R21,R19   ;запись второго информационного бита в регистр R21

      LSR R21   ;сдвиг вправо второго информационного бита в нулевой разряд

      LDS R19,0x0993;запись в регистр R19 исходного  сообщения

      ANDI R19,0x04 ;выделение третьего информационного бита

      MOV R22,R19   ;запись третьего информационного бита в регистр R22

      LSR R22

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

      LDS R19,0x0993;запись в регистр R19 исходного  сообщения

      ANDI R19,0x08 ;выделение четвёртого информационного бита

      MOV R23,R19   ;запись четвёртого информационного бита в регистр R23

      LSR R23

      LSR R23

      LSR R23 ;сдвиг вправо четвёртого информационного бита в 0-й разряд

      STS 0x0995,R20;запись 1-го информационного  бита в ячейку ОЗУ 0995h

      EOR R20,R23

      EOR R20,R22   ;вычесление первого контрольного бита

      STS 0x0996,R20;запись первого контрольного  бита в ячейку ОЗУ 0996h

     LDS R20,0x0995;запись в регистр R20 первого  информационного бита

      EOR R20,R23

     LDS R20,0x0995;запись в регистр R20 первого  информационного бита