Начальные сведения о помехозащищенном кодировании на основе кода Хэмминга

Помехозащищенное кодирование применяется для надёжной передачи данных по каналу связи, в котором может присутствовать источник помех. В МК 1986ВЕ8Т в качестве таких каналов связи выступают шины, осуществляющие передачу данных как между внутренними блоками МК, например, внутренняя память – ядро, так и между внутренними и внешними блоками, например, внешняя память – ядро. Само помехозащищенное кодирование, а также декодирование с коррекцией ошибок, осуществляется на аппаратном уровне с помощью специальных блоков. В качестве используемого самокорректирующегося кода применяется код Хэмминга, при этом в МК используется всего два вида кодовых слов: (7,4) для задания режима работы и (72,64) для внутренней памяти и памяти на внешней шине.

Общий алгоритм генерации ECC и коррекции ошибок на основе кода Хэмминга

Общий алгоритм коррекции ошибок (ECC), основанный на коде Хэмминга, на примере операции записи/чтения:

Начальная информация о коррекции ошибок на основе кода Хэмминга 7,4

Здесь мы рассмотрим построение кода Хэмминга 7,4, чтобы понять, как производится генерация ECC и коррекция одиночных ошибок.

Однако, прежде чем мы приступим к рассмотрению кода Хэмминга (7,4), сделаем небольшое отступление и рассмотрим задачу о надёжной передаче данных в ненадёжном канале связи и разберёмся, откуда появилось условие для кода Хэмминга 2 k >=k+m+1.

Небольшое отступление

Предположим, что мы хотим передать слово B= по каналу связи, в котором действует источник помех (не такая уж и гипотетическая задача). Предположим, что при передаче слова В источник помех может вызвать ошибку не более чем в 1 бите. Передавать слово В в исходном виде дело совершенно не надёжное, и установить, что же в итоге мы хотели передать, будет невозможно. Один из тривиальных способов защиты информации в данном канале: утроить все биты исходного слова (а-ля троированная логика) В’=. Тогда, если при передаче изменится один из битов, то по схеме мажорирования (по принципу большинства), можно восстановить слово В’, а значит, и исходное слово В. Такое решение при передаче данных является некорректным, так как утроение бит приведёт к тому, что в таком длинном слове вероятность появления двойных ошибок резко возрастёт, а исправить их уже не получится. Поэтому необходимо закодировать исходное слово так, чтобы увеличение его длины было минимальным.

Это как раз и сделал Ричард Хэмминг. Он рассмотрел случай, когда при передаче может возникнуть 1 ошибка, и пришёл к выводу, что, передавая закодированное слова длины l = m+k, где m – длина исходного слова, k – длина контрольных бит. Приёмник, с учётом одной ошибки, может получить l+1 различных вариантов передаваемого слова. Например, предаём слово C= длиной 3 бита. До приёмника могут дойти следующие слова:

Итого l+1=4 различных варианта принятого слова. Чтобы закодировать с помощью контрольных бит все эти случаи, необходимо чтобы 2 k >=l+1 или 2 k >= m+k+1. Вот так и появилось знаменитое неравенство для нахождения количества контрольных бит k в зависимости от необходимого количества бит m исходного слова.

Для надёжной передачи 4 бит информации (m), исходя из выше указанного неравенства, необходимо к ним добавить ещё 3 проверочных бита (k).

В обозначении 7,4 первое число (7) определяет количество бит закодированного слова, второе (4) – количество бит исходного слова.

Вычисление проверочных разрядов r[2:0] выполняется по формулам:

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

Для математического описания кодирования и декодирования исходных слов вводят специальные матрицы: матрицу G генерации и матрицу H проверки.

Матрица генерации G формирует закодированное слово путём перемножения слова A и матрицы генерации G.

X = AG, при этом операция суммирования производится по модулю 2.

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

 Перемножение вектора А на матрицу В

При перемножении матриц для кодирования Хэмминга вместо «+» используется ⊕.

Матрица G для кода 7,4 выглядит следующим образом:

 Матрица генерации для кода Хэмминга 7,4

Операция перемножения A на G:

 Перемножение вектора А на матрицу G

Таким образом перемножив A на G мы получим закодированное слово X, состоящее из слова A и проверочных бит r[2:0].

При чтении закодированного слова X заново выполняется расчёт контрольных бит на основе слова А, а затем вычисленные и считанные контрольные биты складываются по модулю 2. Результат сложения образует так называемый синдром S = . По синдрому определяется ошибка, если таковая была.

S2 = r2 ⊕ r2’ = r2 ⊕ a3 ⊕ a2 ⊕ a1 ;

S1 = r1 ⊕ r1’ = r1 ⊕ a3 ⊕ a2 ⊕ a0 ;

S0 = r0 ⊕ r0’ = r0 ⊕ a3 ⊕ a1 ⊕ a0 ;

где r[2:0]’ – заново вычисленные проверочные биты на основе считанного слова А.

Для расчёта синдрома S[2:0], аналогично матрицы генерации G, вводят проверочную матрица H. Синдром формируется путём перемножения считанного слова X и транспонированной проверочной матрицы H T :

Проверочная матрица H для кода Хэмминга 7,4 имеет вид:

 Проверочная матрица для кода Хэмминга 7,4 (S2,S1,S0)

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

Если поменять местами строки 1 и 3, то получим проверочную матрицу, указанную в спецификации, при этом изменится порядок следования бит синдрома S = :

 Проверочная матрица для кода Хэмминга 7,4 (S0,S1,S2)

Операция перемножения X на H T (H матрица как в спецификации):

 Перемножение вектора X на матрицу H

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

 Проверочная матрица для кода Хэмминга 7,4 (S0,S1,S2)

К сожалению, данный код Хэмминга (7,4) может применяться только в условиях возникновения однократных ошибок. Если произойдет две и более ошибки, то отличить их от одинарной не получится, а поэтому в данном случае исправление одной ошибки не приведёт к восстановлению исходного слова.

Чтобы этого избежать, вводят дополнительный бит четности p (parity), с помощью которого можно определить, произошла одиночная ошибка либо двойная и более. Тогда, если имеет место однократная ошибка, слово можно исправить, если двукратная – слово восстановлению не подлежит.

Бит чётности может занимать любую позицию в закодированном слове, но для определённости мы сделаем, как указано в спецификации, и добавим его на место 4 бита. При этом закодированное слово X приобретёт вид:

Бит чётности p вычисляется на основе всех остальных бит слова X путём их сложения по модулю 2:

При определении ошибки заново вычисляется бит чётности p’ и складывается со считанным битом p, при это данный результат будет являться новым битом синдрома. Так как мы добавили бит чётности на 0 позицию проверочных бит, то слово синдрома S = приобретёт следующий вид:

S0 = p ⊕ p’ = p + r2 ⊕ r1 ⊕ r0 ⊕ a3 ⊕ a2 ⊕ a1 ⊕ a0 ;

S1 = r0 ⊕ r0’ = r0 ⊕ a3 ⊕ a1 ⊕ a0 ;

S2 = r1 ⊕ r1’ = r1 ⊕ a3 ⊕ a2 ⊕ a0 ;

S3 = r2 ⊕ r2’ = r2 ⊕ a3 ⊕ a2 ⊕ a1 ;

С учётом бита чётности проверочная матрица H будет иметь вид:

 Проверочная матрица для кода Хэмминга 7,4 c битом чётности (S1,S2,S3,S0)

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

 Проверочная матрица для кода Хэмминга 7,4 c битом чётности (S1,S2,S3,S0)

Для кода Хэмминга (72,64) генерации ECC и коррекция ошибок осуществляется точно таким же образом, просто используемые матрицы немного больше. Надо заметить, что для кода (72, 64) расстояние Хэмминга позволяет определять двойные ошибки, а потому бит чётности в данном коде не используется.

Программная генерация ECC

В спецификации приведён пример программного вычисления проверочных бит ЕСС для кода Хэмминга (72, 64). Как уже было отмечено ранее, в данном коде не используется бит чётности, поэтому алгоритм вычисления ECC для кода (7,4) с битом чётности будет отличаться от алгоритма для кода (72,64). В связи с этим мы разберём здесь программную реализацию вычисления ECC для кода (7,4) c битом чётности на примере вычисления бит CFGx в режимах запуска EXTBUS_CFG+JB и EXTBUS_CFG+JA.

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

Полный код функции представлен ниже:

Разберём основные части.

Для начала составим из правой части проверочной матрицы H массив генерации ECC G[], при этом каждый элемент данного массива будет представлять строку правой части матрицы H. Далее в цикле формируем проверочные биты, путем выборки необходимые информационные биты, а именно, накладывая маску из массива генерации, после чего суммируем их по модулю два. Делаем это для трёх проверочных бит. Дописываем их к информационным битам. После вычисляем бит чётности p суммированием по модулю два всех проверочных и информационных бит, и дописываем его в кодируемое слово. Исходное слово закодировано.

Курсовая работа Код Хемминга
учебно-методическое пособие по информатике и икт (10, 11 класс) по теме

Коробейникова Ольга Витальевна

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

Скачать:

Предварительный просмотр:

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

«Омский государственный педагогический университет»

Факультет математики, информатики, физики и технологии

Кафедра прикладной информатики и математики

Направление: педагогическое образование

Профиль: Информатика и Технология

Дисциплина: Теоретические основы информатики

«__» _______________ 20___г.

Введение

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

История развития помехоустойчивого кодирования началась еще с 1946г., а именно, после публикации монографии американского ученого К. Шеннона «Работы по теории информации и кибернетике».В этой работе он не показал как построить эти коды, а доказал их существование. Важно отметить, что результаты работы К. Шеннона опирались на работы советских ученых, таких как: А. Я. Хинчин, Р. Р. Варшамов и др. На сегодняшний день проблема передачи данных является особо актуальной, т.к. сбой при передаче может вызвать не только искажение сообщения в целом, но и полную потерю информации. Для этого и существуют помехоустойчивые коды, способные предотвратить потерю и искажение информации. В настоящее время существует ряд разновидностей помехоустойчивых кодов, обеспечивающих высокую достоверность при малой величине избыточности и простоте технической реализации кодирующих и декодирующих устройств. Принципиально коды могут быть использованы как для обнаружения, так и для исправления ошибок. Однако удобства построения кодирующих и декодирующих устройств определили преимущественное применение лишь некоторых из них, в частности корректирующего кода Хемминга.

Цель данной курсовой работы: Ознакомление с помехоустойчивым кодированием и изучение кода Хемминга.

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

2) Ознакомиться с кодом Хемминга, как с одним из видов помехоустойчивого кодирования;

3) Изучить алгоритм построения кода Хемминга.

Объект исследования : помехоустойчивое кодирование.

Предмет исследования : код Хемминга.

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

Глава 1. Теоретические основы изучения помехоустойчивого кодирования

1.1. Виды помехоустойчивого кодирования

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

Рис. 1.Помехи и их источники

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

Приведем классификацию помехоустойчивых кодов.

1) Обнаруживающие ошибки:

2) Корректирующие коды:

А) С пороговым декодированием;

Б) По макс. правдоподобия;

В) С последовательным декодированием.

Теперь рассмотрим более подробно каждый вид кодирования.

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

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

Начальные данные: 1111

Данные после кодирования: 11110 (1 + 1 + 1 + 1 = 0 (mod 2))

Принятые данные: 10110 (изменился второй бит)

Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка [3].

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

Элементы данного кода заменяются двумя символами, единица «1» преобразуется в 10, а ноль «0» в 01.

Вместо комбинации 1010011 передается 10011001011010. Ошибка обнаруживается в том случае, если в парных элементах будут одинаковые символы 00 или 11 (вместо 01 и 10) [2].

Код с постоянным весом.

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

Число разрешенных кодовых комбинаций в кодах с постоянным весом определяется как количество сочетаний из n символов по g и равно

Рис.2. Примеры разрешенных и запрещенных комбинаций кода МТК-3

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

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

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

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

Для перевода простого двоичного кода в код Грея нужно:

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

1.2.Характеристика кода Хэмминга при помехоустойчивом кодировании

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

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

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

(r – количество проверочных разрядов).

Рис.3. Проверочная матрица

Перестановкой столбцов, содержащих одну единицу, данную матрицу можно привести к виду(рис.4)

Рис. 4.Измененная матрица

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

Рис.5. Система проверочных уравнений

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

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

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

1.3.Алгоритмы использования кода Хэмминга для нахождения ошибок

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

Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

Количество разрядов m – определяет количество проверок.

В третью проверку – коэффициенты которые содержат 1 в третьем разряде и т. д.

Источники:

https://startmilandr. ru/doku. php/prog:spec:hammingcode? do=export_xhtml

https://nsportal. ru/shkola/informatika-i-ikt/library/2016/10/03/kursovaya-rabota-kod-hemminga

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: