Hamming-Code

[object Object]
[object Object]

Введение

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

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

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

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

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

: помехоустойчивое кодирование.

: код Хемминга.

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

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

[object Object]

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

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

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

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

Характерной особенностью проверочной матрицы кода с Hamming-Codeявляется то, что ее столбцы представляют собой любые различные ненулевые комбинации длиной =5 для кода (15,11), проверочная матрица может иметь следующий вид (рис.3)

http://info.sernam.ru/archive/arch.php?path=../htm/book_codb/files.book&file=codb_28.files/image4.gif

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

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

http://info.sernam.ru/archive/arch.php?path=../htm/book_codb/files.book&file=codb_28.files/image5.gif

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

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

http://info.sernam.ru/archive/arch.php?path=../htm/book_codb/files.book&file=codb_28.files/image6.gif

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

Hamming-CodeHamming-CodeHamming-CodeHamming-Code

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

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

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

[object Object]

ЗАКЛЮЧЕНИЕ

[object Object]

Список литературы

  1. ,свободный. Дата обращения: 27.11.2015.
  2.  свободный. Дата обращения: 05.12.2015.
  3. ,свободный. Дата обращения: 27.11.2015.
  4. , свободный. Дата обращения: 27.11.2015.
  5.  свободный. Дата обращения: 27.11.2015
  6.  свободный. Дата обращения: 05.12.2015
  7. , свободный. Дата обращения: 06.12.2015.
  8. , открытый. Дата обращения: 20.12.2015.
Читайте также:  Xbox 360 slim код ошибки 0020

Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей Hamming-Codeстрок и Hamming-Codeстолбцов, причем столбцами H(n,k) являются все различные ненулевые двоичные последовательности длины m (m – разрядные двоичные числа от 1 до Hamming-Code).

Длина кодовой комбинации кода Хэмминга равна Hamming-Code.

Число информационных элементов определяется как Hamming-Code.

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

Зная вид матрицы H(n,k), можно определить корректирующие свойства (n, k) – кода Хэмминга. Так как все столбцы матрицы проверок различны, то никакие два столбца H(n,k) не являются линейно зависимыми. Наряду с этим, для любого числа m всегда можно указать три столбца матрицы H(n,k), которые линейно зависимы, например, столбцы, соответствующие числам 1, 2, 3. Следовательно, для любого (n, k) – кода Хэмминга dmin =3.

Код Хэмминга является одним из немногочисленных примеров совершенного кода.

Действительно, поскольку (n, k) – код Хэмминга исправляет все одиночные ошибки, то все образцы одиночных ошибок (а их всего насчитывается Hamming-Codeвариантов) должны разместиться в различных смежных классах, число которых также равно Hamming-Code. Следовательно, помимо смежных классов, содержащих образцы одиночных ошибок, никаких других в таблице декодирования не имеется, что и подтверждает совершенность кода Хэмминга.

При фиксированном числе Hamming-Codeможно построить код Хэмминга любой длины (Hamming-Code) путем укорочения (n, k) – кода. Укорочение не уменьшает минимальное кодовое расстояние. В силу того, что для любого числа n существует код Хэмминга, любой групповой код с исправлением одиночных ошибок принято называть кодом Хэмминга.

Пример 5.13. Определим параметры кодов Хэмминга естественной длины для различных значений m. Результаты представим в виде таблицы.

m Hamming-Code k Hamming-Code
       
      0,33
      0,57
      0,74
      0,84
      0,91
      0,95

и т.д.

Очевидно, что минимальная длина кода Хэмминга, имеющего практическое значение, есть 3. При увеличении n отношение Hamming-Codeвозрастает и стремится к 1.

Пример 5.14. Рассмотрим код Хэмминга (7,4). Матрица проверок этого кода состоит из 7 трехразрядных двоичных чисел от 1 до 7:

Hamming-Code.

Из рассмотрения этой матрицы видно, что минимальное число линейно зависимых столбцов равно 3(к примеру 1, 2 и 3), следовательно, dmin =3.

В том случае, когда столбцы матрицы H(n,k) – кода Хэмминга есть упорядоченная запись m – разрядных двоичных чисел, декодирование осуществляется оригинальным образом. В результате вычисления проверочного соотношения для кодовой комбинации Hamming-Code, имеющей одиночную ошибку, получается синдром Hamming-Codeв точности равный номеру элемента, в котором произошла ошибка.

Действительно, если ei содержит одну единицу в разряде, соответствующем ошибочному элементу, то при умножении на матрицу НТ все строки матрицы НТ, соответствующие нулям в ei, обращаются в нули, и лишь строка, соответствующая “1” в ei сохраняет свой вид (т.е. порядковый номер элемента в двоичной записи) в ответе.

Пример 5.15. Пусть приемник УЗО системы передачи данных зарегистрировал комбинацию Hamming-Code. Вычисление синдрома дает

Hamming-Code,

т.е. ошибка в четвертом элементе и кодовая комбинация кода (7,4), которая была передана, имеет вид: Hamming-Code

Путем несложных преобразований из (n, k) – кода Хэмминга с dmin =3 можно получить (n +1, k) – код Хэмминга с dmin =4.

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

Матрица проверок для (n +1, k) – кода Хэмминга с dmin =4 получается из матрицы проверок (n, k) – кода с dmin =3 путем введения дополнительной строки из (n +1)-ой единицы.

Так как размерность матрицы проверок кода с dmin =4 должна быть равна Hamming-Code, то к каждой строке матрицы проверок кода с dmin =3, необходимо добавить один нулевой элемент для того, чтобы не нарушить введенные ранее проверки. Матрица проверок для (n +1, k) – кода dmin =4 имеет вид:

Читайте также:  Коды ошибок вольво в100в13

Hamming-Code,

где H(n,k) = матрица проверок исходного кода с dmin =3.

Рассмотренная процедура, приведшая к удлинению кодовой комбинации на один разряд при увеличении dmin на 1 единицу, получила название удлинения кода (1- удлинение).Удлинению могут быть подвергнуты и другие коды, например, коды Рида-Соломона.

Пример 5.16. Построить код Хэмминга (8,4) с dmin =4 на основе матрицы проверок кода (7,4).

Известно:

Hamming-Code

По виду матрицы Hamming-Codeможно сделать вывод о том, что в коде (7,4) осуществляется 3 независимые проверки на четность.

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

Таким образом, матрице Hamming-Codeсоответствует следующая система проверочных соотношений:

Hamming-Code

Для того, чтобы получить код (8,4) с dmin =4 вводим еще одну проверку по всем элементам кодовой комбинации, а результат этой проверки записывается в виде дополнительного 8-го элемента:

Hamming-Code

или

Hamming-Code.

Этой проверке соответствует дополнительная (четвертая) строка в матрице Н (8,4), состоящая из восьми единиц. Для того чтобы не нарушить три предыдущие проверки на месте восьмого элемента в трех первых строках матрицы Н (8,4) на месте восьмого элемента, проставляем нули. Итак, матрица проверок кода (8,4) получена в виде:

Hamming-Code.

Определим известным способом dmin (8,4) – кода. Из рассмотрения тех столбцов, сумма которых давала нулевой столбец в (7,4) – коде, видно, что с добавлением 4-ой строки они перестали быть линейно зависимыми. Теперь уже число линейно зависимых столбцов должно быть четным и минимум 4, например, 3 первые столбца и последний. Таким образом, для полученного кода Хэмминга (8,4) dmin =4.

До сих пор мы еще не разделили элементы кодовой комбинации на информационные и проверочные. Наиболее рационально, по-видимому, это можно сделать следующим образом. Желательно, чтобы каждое проверочное соотношение однозначно определяло проверочный элемент как результат проверки на четность некоторой совокупности информационных элементов. В таком случае мы получили бы возможность определять значение проверочного элемента наиболее простым образом – решением одного линейного уравнения с одним неизвестным. Для этого при упорядоченной записи столбцов матрицы H(n,k) в качестве проверочных элементов необходимо брать элементы с номерами 2 i, где i изменяется от 0 до m -1, так как именно эти столбцы содержат только по одной единице. Последнее свидетельствует о том, что элементы с номерами 2 i входят только в одну проверку и, следовательно, они могут быть взяты в качестве проверочных.

Пример 5.17. Определить местоположение проверочных элементов к коде Хэмминга (7,4).

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

Hamming-Code

Зная места проверочных элементов, легко привести матрицу H(n,k) кода Хэмминга к канонической форме.

Для этого необходимо столбцы с номерами 2 i, где Hamming-Codeпри упорядоченной записи столбцов переместить на места m первых столбцов в порядке убывания номеров. В общем виде такая перестановка столбцов в матрице H(n,k) приводит к эквивалентному (n, k) – коду. В случае же кодов Хэмминга естественной длины код получается даже не эквивалентный, а в точности совпадающий с исходным кодом.

Пример 5.18. Преобразовать матрицу Hamming-Codeк канонической форме.

Читайте также:  Что это код ошибки system service exception windows

Hamming-Code

Переставим столбцы: 4-ый на место 1-го, 1-ый на место 3-го, а 3-ий на место 4-го:

Hamming-Code.

Это и есть каноническая форма матрицы Hamming-Code. Сравнение ее с исходной матрицей Hamming-Codeпоказывает, что местам информационных элементов в канонической форме соответствуют столбцы с номерами 3, 5, 6, 7, а местам проверочных элементов – столбцы 4, 2, 1.

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

Hamming-Code

Порождающую матрицу G(n, k) для кода Хэмминга можно получить из матрицы H(n,k), используя теорему 5.3:

Hamming-Code

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

Оценим эффективность кодов Хэмминга.

а) Коды Хэмминга с dmin=3

Такие коды используются либо для исправления ошибки кратности t =1, либо для гарантийного обнаружения ошибок кратности S =2. Соответственно, вероятность ошибки для этих случаев в канале с группированием ошибок равна:

Hamming-Code.

Выигрыш по достоверности по сравнению с простыми кодами той же длины составляет:

Hamming-Code

Hamming-Code

б) Коды Хэмминга с dmin=4.

Для таких кодов возможны два режима – исправление однократных ошибок и обнаружение ошибок и только обнаружение ошибок. Вероятность ошибки для этих режимов в случае группирования ошибок равна:

Hamming-Code

Hamming-Code

Выигрыш по достоверности по сравнению с простым кодом той же длины составляет:

Hamming-Code.

5.4.3Итеративные коды.

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

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

Hamming-CodeHamming-Code 5 эл. комбинация

Рис.5.6.

 
  Hamming-Code

               
    Hamming-Code
 
    Hamming-Code   Hamming-Code
  Hamming-Code
 
 

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

Теорема 5.3. Минимальное кодовое расстояние итеративного кода равно произведению минимальных кодовых расстояний, кодов, его составляющих.

Действительно, если в случае двух проверок минимальный вес одного кода равен Hamming-Code, а другого Hamming-Code, то вектор итеративного кода имеет, по крайней мере, Hamming-Codeединиц в каждой строке и Hamming-Codeэлементов в каждом столбце и, следовательно, не менее Hamming-Codeединиц.

Аналогичные рассуждения можно продолжить и на случай большего числа проверок.

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

Пусть GA – порождающая матрица кода, используемого для проверки по строкам, а GВ – порождающая матрица кода, используемого для проверки по столбцам, тогда порождающая матрица итеративного кода (GAВ) имеет вид:

Hamming-Code.

Запись Hamming-Codeозначает, что на местах “1” в матрице GA записывается матрица GВ, а вместо “0” записывается матрица из одних нулей, размеры которой равны размерам GВ. Так, например, если для проверки по строкам и столбцам используется (6, 5) – код с проверкой на четность, то

Hamming-Code,

где

Hamming-Code.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *