История создания двоичного циклического кода Хемминга для защиты памяти в компьютерной технике. Принципы кодирования и алгоритм декодирования информации. Принципиальная схема кодера. Логика построения программного декодера несистематического кода.
Аннотация к работе
[1] Первая работа по теории кодирования была опубликована известным ученым Ричардом Уэсли Хэммингом в 1950 году. Привело его к этой работе следующее: после окончания университета он занимался тем, что сейчас бы назвали численными методами, и работал сначала в Лос-Аламосе над Манхэттенским проектом, то есть над созданием ядерной бомбы, а потом почти сразу, в 1946 году, перешел в Bell Labs. Там он продолжал заниматься численными методами, решать уравнения на первых вычислительных машинах. Программисты того времени, чтобы бороться со сбоями, делили задачу на этапы, и после каждого этапа программа должна была записать или распечатать результаты. Когда работа шла неверно, когда они обнаруживали ошибку, то звучал сигнал тревоги, и работа прекращалась.Позволяет исправлять одиночную ошибку (ошибка в одном бите) и находить двойную. Построение кодов Хэмминга основано на принципе проверки на четность числа единичных символов: к последовательности добавляется такой элемент, чтобы число единичных символов в получившейся последовательности было четным. знак здесь означает сложение по модулю 2. Такой код называется или . На вход декодера поступает кодовое слово где штрихом помечены символы, которые могут исказиться в результате помехи. В декодере в режиме исправления ошибок строится последовательность синдромов: называется синдромом последовательности.Линейный код называют циклическим, если для любого кодового слова [xn, x0, x1... xn-1] циклическая перестановка символов [x0 x1... xn-1 xn] также дает кодовое слово. Например, считая, что коэффициенты записаны в порядке возрастания степени, сообщение [1010] запишем в виде многочлена 1 x2. Кодирование сообщения в более "длинное" кодовое слово будет проводится умножением этого многочлена на другой, что дает в результате многочлен более высокой степени. Замечательным свойством полиномиального представления кодов является возможность осуществить циклический сдвиг на одну позицию вправо простым умножением кодового многочлена степени n - 1 на многочлен "x" и нахождения остатка от деления на 1 xn. Процедура кодирования в полиномиальной интерпретации сводится к умножению многочлена-сообщения на подходящий неприводимый в поле GF(2) многочлен, называемый порождающим многочленом данного кода.Алгоритм декодирования следующий: 1) Найти синдром или синдромный многочлен s(x) = r(x)mod g(x), где r(x) полученное кодовое слово. 2) Для каждого i = 0…j, вычислять si(x) = xis(x)mod g(x) до тех пор, пока не будет найден, sj такой, что для него (вес) wt(sj) ? t, где t - максимальное число ошибок (в данной работе t = 1), исправляемых кодом. Найдем синдромный многочлен, для этого нужно найти остаток от деления многочлена r(x) на многочлен g(x). s(x) = r(x)mod g(x); s(x) = x2 1 В соответствии с описанной процедурой декодирования будем вычислять: si(x) = xi(x 1)mod g(x) для последовательных возрастающих значений i пока не найдем многочлен степени меньшей или равной одному (число ошибок t = 1). s1 = xs(x)mod g(x) = 1 1 имеет вес 1 для нахождения многочлена ошибок вычисляем: e(x) = x7-1(1)mod(xn 1) = x6Введем логику построения Декодера несистематического кода Хэмминга. 1) На вход подается кодовое слово, принятое с ошибкой или без 2) Кодовое слово делится на порождающий многочленКоды Хэмиинга позволяют исправлять как одиночные, так и множественные ошибки.
План
Оглавление
1. История создания кода Хемминга
2. Код Хемминга
3. Циклический несистематический (7,4) код Хемминга
4. Логика построения программного декодера несистематического кода
5. Декодирование
6. Логика построения программного декодера несистематического кода Хэмминга
Заключение
Список литературы
Приложение
1. История создания кода Хемминга
Вывод
Коды Хэмиинга позволяют исправлять как одиночные, так и множественные ошибки. Так как это был один из первых кодов на практике он используется все реже, но на практике они до сих пор используются для защиты памяти в компьютерах.
В данной курсовой работе, мы рассмотрели способы реализации кодера/декодера несистематического циклического кода Хэмминга в программном виде.
Список литературы
1. Материалы сайта https://ru.wikipedia.org.
2. Учеб. пособие для вузов / М.В. Гаранин, В.И. Журавлев, С.В. Кунегин. -М.: Радио и связь, 2001. - ISBN: 5-256-01475-7.
3. Феер К. Беспроводная цифровая связь. Методы модуляции и расширения спектра. Пер. с англ. - М.: Радио и связь, 2000. ISBN 5-256-01444-7.
4. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. - М.: Радио и связь, 1987. - 392 с.
5. Теория электрической связи: Учеб. для вузов/ А.Г. Зюко, Д.Д. Кловский, В.И. Коржик, М.В. Назаров; Под ред. Д.Д. Кловского. - М: Радио и связь, 1999.