Корректирующий код Хэмминга

Размещено на http://www.allbest.ru/

Российский государственный университет Нефти и Газа имени И.М.Губкина

« КОРРЕКТИРУЮЩИЙ КОД ХЭММИНГА»

ВЫПОЛНИЛА: СТУДЕНТКА ГР. АС-13-05

АБДУЛЛАТИПОВА А.

преподаватель: АНИЩЕНКО И.В.

МОСКВА 2016

Ричард Хэмминг и начало теории кодирования

В книге Стефана Цвейга “Звездные часы человечества” есть замечательный рассказ “Гений одной ночи” об офицере французской армии Руже де Лиле, написавшем в течение одной ночи в пылу охватившего его вдохновения знаменитую “Марсельезу”. Это было в 1792 г. в революционном Марселе. Песня в течение нескольких дней распространилась по Франции, быстро приобрела колоссальную популярность во всём мире и впоследствии стала национальным гимном Французской республики. История сохранила имя Руже в памяти потомства благодаря этой единственной песне.

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

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

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

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

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

Краткая биография

Ричард Весли Хэмминг родился 11 февраля 1915 г. в Чикаго. В 1937-м он окончил Чикагский университет и получил степень бакалавра. Он продолжил образование в университете штата Небраска, где в 1939 г. ему была присвоена следующая - магистерская степень. В 1942 г. Ричард стал доктором философии в области математики в университете штата Иллинойс.

В 1945-м Хэмминг участвовал в знаменитом Манхэттенском исследовательском проекте, целью которого было создание атомной бомбы.

А с 1946 г. в лаборатории Белла он начинает заниматься конструированием компьютеров. В этом знаменитом центре, где трудились К. Шеннон и многие другие выдающиеся учёные, ему суждено было проработать почти тридцать лет.

В 1976 г. Ричард переезжает в город Монтеррей (шт. Калифорния) и возглавляет научные исследования в области вычислительной техники в Высшем военно-морском училище. В этом училище он преподавал и писал книги по теории вероятностей и комбинаторике.

Пионерская работа Хэмминга была отмечена многими наградами. В 1968-м он стал почетным членом Института инженеров по электротехнике и электронике (IEEE) и был награжден премией Тьюринга Ассоциации компьютерных технологий. За исключительный вклад в развитие информационных наук и систем в 1979 г. ему присуждена премия Эммануила Пиоре. В 1980-м его избрали членом Национальной Академии инженерных наук, в 1981-м он получил премию Гарольда Пендера от Пенсильванского университета, а в 1988-м - почетную медаль IEEE. В 1996 г. в Мюнхене за работу по кодам, корректирующим ошибки, Хэмминг был удостоен престижной премии Эдуарда Рейма в размере $130 000.

Скончался Ричард Хэмминг 7 января 1998 года в возрасте 82 лет.

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

Работы, заложившие основы теории кодирования

Коды, способные корректировать ошибки (в каналах связи в цифровых вычислительных машинах и т. п.) при обработке сигналов, были предложены Хэммингом еще до 1948 г., когда была опубликована знаменитая статья Шеннона “Математическая теория связи”, заложившая прочную основу теории в данной области.

В этой статье Шеннон, ссылаясь на исследование, выполненное в 1947 г. его сослуживцем по лаборатории Белла Ричардом Хэммингом, описал в качестве примера простой код длины 7, корректирующий все одиночные ошибки. Публикация же оригинального материала Хэмминга по патентным соображениям была задержана до апреля 1950-го. Следует отметить, что пример корректирующего ошибки кода, приведенный в упомянутой статье Шеннона, инициировал исследование другого американского ученого, М. Е. Голея. Голей независимо от Хэмминга открыл коды, корректирующие одиночные ошибки. В 1949 г. (т. е. раньше Хэмминга) он опубликовал короткую заметку (всего на полстраницы) о своих результатах в Трудах IЕЕE. В этой заметке он рассмотрел не только бинарные коды, но и коды общего вида, комбинации которых принадлежат конечному полю (математическому множеству элементов с определенными операциями сложения, вычитания, деления и умножения) с рⁿэлементами (р - простое, а n - целое число).

Надо отметить, что ряд основополагающих идей теории связи был известен в качестве частных математических результатов ещё до того, как их начали применять учёные, решающие проблемы передачи сообщений по каналам связи. В своей книге “Алгебраическая теория кодирования” крупный американский специалист в области теории кодирования Э. Берлекамп сделал весьма интересное замечание. Он отметил, что конструкция кодов Хэмминга была описана в ином контексте ещё в 1942 г. известным американским математиком Р. А. Фишером, в работе посвященной теории факторного анализа (одного из разделов математической статистики) и её связи с математической теорией групп. Кстати, теорема В. А. Котельникова, указывающая на возможность представления аналоговых сигналов в цифровом виде, тоже была открыта как один из частных математических результатов теории интерполяции функции ещё в начале ХХ века английскими математиками Е. Т. и Дж. М. Уиткерами. Следует подчеркнуть, что ни Фишер, ни упомянутые английские ученые не связывали свои результаты с важнейшими для современного мира проблемами передачи информации по каналам связи.

Вольфганг Гёте говорил: “Недостаточно только получить знание; надо найти ему приложение. Недостаточно только желать; надо делать”. Для теории и техники связи теорема Котельникова и коды Хэмминга имеют исключительное значение, поскольку именно благодаря им перед инженерами открылась ясная перспектива создания цифровых систем, которые в конце ХХ века произвели революцию в электросвязи и поэтому их с полным основанием называют именами этих учёных.

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

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

В этом выражении число ошибок e может быть исправлено корректирующим блочным кодом длиной N, имеющим М кодовых комбинаций (C^j_N - биномиальный коэффициент).

Работа Хэмминга сыграла ключевую роль в последующем развитии теории кодирования и стимулировала обширные исследования, выполненные в последующие годы. В 1956 г. Давид Слепян первым изложил теорию кодов с проверкой четности на серьезной математической основе. Главный сдвиг в области теории кодирования произошел, когда французский ученый А. Хоквингем (1959 г.) и американцы Р. К. Боуз и Д. К. Рой-Чоудхури (1960 г.) нашли большой класс кодов (коды БЧХ), исправляющих кратные ошибки. Американские исследователи И. С. Рид и Г. Соломон (1960 г.) нашли связанный с кодами БЧХ класс кодов для недвоичных каналов.

В 1980 г. Хэмминг написал блестящий учебник “Теория кодирования и теория информации”, который в 1983 г. был переведен на русский язык. Эту книгу, как и другие его труды, отличает оригинальность постановки вопросов, популярность изложения, глубокое понимание практических задач, корректность и разумная степень строгости математической трактовки затронутых вопросов. Изложение материала построено таким образом, что читателю интуитивно понятно, почему справедлива та или иная теорема.

Описание кодирования по Хэммингу

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

Исходными данными для кодирования является произвольная двоичная последовательность, например как это изображено на рисунке 1.1.

Исходная битовая последовательность

Рис. 1.1

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

m = 2^r _ r - 1,

где r - любое целое число большее 2. Куски исходной двоичной последовательности будем называть «блоки исходного кода» и обозначать a_i. Рассмотрим для определенности r = 4, тогда m = 11. Cоответствующее деление исходной битовой последовательности на блоки исходного кода изображено на рис. 1.2.

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

Позиции с номерами 2ⁱ (i = 1, 2, …r) резервируются под контрольные биты;

в остальные биты копируется исходный код в порядке следования его битов.

Расширенные блоки будем называть «блок кода» и обозначать b_i. Расширение исходного кода для r = 4 и n = 15 продемонстрировано на рис. 1.3.

Затем вычисляют контрольные разряды. Для вычисления контрольных разрядов нужна вспомогательная матрица M размером (2^r - 1) строк и r столбцов. Матрица заполняется по строкам, в каждую строку записывают двоичное представление чисел от 1 до 2^r - 1, младшие биты пишут ПЕРВЫМИ. Такая матрица для r = 4 показана на рис. 1.4. Далее вычисляются контрольные разряды c_i, для этого из матрицы M выбираются и суммируются по колонкам все строки номера которых совпадают с ненулевыми битами блока кода b_i. Полученная строка из r битов записывается в контрольные разряды блока кода b_i в порядке следования битов, как показано на рис. 1.4. Вычисление контрольных разрядов c_i можно представить матричным умножением

c_i = (b_i)^TM,

здесь (b_i)^T -- строка (вместо столбца) расширенного кода, где контрольные биты равны 0.

Полученные блоки кода можно вновь преобразовать в битовую последовательность и передавать по каналу связи. Код Хемминга способен детектировать и исправлять 1 (одну) ошибку на блок.

Разделение битовой последовательности на блоки исходного кода

Размещено на http://www.allbest.ru/

Рис. 1.2 Расширение блоков исходного кода контрольными разрядами

Размещено на http://www.allbest.ru/

Рис. 1.3

Описание декодирования и исправления ошибки по Хэммингу

Переданная по информационному каналу в приемник битовая последовательность делится на куски по n = 2^r - 1 бит -- получаются блоки кода. С каждым таким блоком выполняется операция

c_i = (b_i)^TM,

здесь (b_i)^T -- строка (вместо столбца) расширенного кода. Пример приведен на рис. 1.5. Причем здесь контрольные разряды участвуют в вычислении суммы.

Если получено, что все биты c_i равны нулю, то значит ошибок нет и коррекция не нужна, см. рис. 1.5. Если хотя бы один бит c_i не равен нулю (см. рис. 1.6), то имела место ошибка. Значение c_i преобразуют из битового представления в десятичное число i и бит блока кода с номером i -- ошибочный бит (передан с ошибкой). Для исправления значение бита инвертируют: заменяют ноль на единицу, а единицу на ноль. В результате получаем правильное значение блока кода.

В заключение, контрольные разряды удаляются из блока и получается блок исходного кода. Эту операцию (проверка-коррекция) проводят с каждым блоком кода.

Вычисление контрольных разрядов

Размещено на http://www.allbest.ru/

Рис. 1.4

Невозможность коррекции двойных ошибок и любых ошибок большей кратности

Две и более ошибки в блоке кода Хэмминга невозможно исправить, хуже того невозможно отличить ошибку в одном бите и ошибку в двух и более битах.

Невозможность исправления двойной ошибки следует и простого факта - процедура коррекции (см. пункт 1.2.) всегда вычисляет один номер ошибочного бита, следовательно, второй и т.д. ошибочные биты просто невозможно указать. Пример двойной ошибки приведен на рис. 1.7.

Невозможность отличить ошибку в одном блоке от ошибки в двух и более блоках следует из факта - процедура коррекции (см. пункт 1.2.) всегда вычисляет один номер ошибочного бита в пределах допустимых номеров, следовательно, отличить случай одиночной ошибки от кратной невозможно.

Проверка на ошибки -- нет ошибок

Размещено на http://www.allbest.ru/

Рис. 1.5

Основные недостатки кода Хэмминга

Главным недостатком кода Хэмминга является не кратность размера исходного блока кода и блока кода степени двойки. Это обстоятельство затрудняет обработку кодов Хэмминга на компьютерах, которые оперируют порциями данных кратными степени двойки (8, 16, 32, 64 бит и т.д.).

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

Проверка на ошибки и коррекция ошибок

Размещено на http://www.allbest.ru/

Рис. 1.6 Проверка на ошибки и невозможность коррекции ошибок кратности два и выше

Пусть 9-й бит передан неправильно, см. рис. 1.5. Как видно, сумма строк вспомогательной матрицы дает номер бита с ошибкой.

Размещено на http://www.allbest.ru/

Рис. 1.7

Демонстрационная программа

Состав демонстрационной программы

Для лучшего понимания процесса кодирования разработана демонстрационная программа (далее просто «программа»). Программа реализована в пакете MathCAD 2001i и может работать на любой более новой версии пакета MathCAD.

Программа состоит из двух файлов

«Вспомогательные функции.mcd» -- содержит определения вспомогательных функций, необходимых для преобразования чисел в двоичные векторы и работы с двоичным представлением числа. Функции этой части программы здесь не описываются, ознакомится с ними и их описанием можно прямо в указанном файле.

«Кодирование Хэмминга.mcd» -- содержит определения основных функций для генерации кода Хэмминга и работы с этим кодом (коррекция ошибок, преобразование кода в строку символов и обратно, и т.п.). В этом же файле приведен пошаговый пример генерации кода Хэмминга из произвольной текстовой строки, пример исправления одиночных ошибок и пример невозможности исправить двойные ошибки или ошибки большей кратности.

Программа реализована для целей обучения поэтому эффективность (скорость кодирования) принесена в жертву максимальной простоте и наглядности процесса.

Описание основных функций демонстрационной программы

Программа состоит из следующих функций. Примеры работы каждой из функций доступны в файле «Кодирование Хэмминга.mcd» справа рядом с определение соответствующей функции.

str2vec(s) -- переводит символы текстовой строки s в ASCII коды (целые числа от 0 до 255). Это встроенная функция и ее описание доступно в справке пакета MathCAD.

BinVec(v, l) -- перевод вектора v, состояшего из неотрицательных целых чисел, в двоичный вектор. Каждое число преобразовывается в вектор двоичного кода длиной l. Все вектора последовательно записываются в результирующий вектор. Определение функции

Определение достаточно простое и не требует разъяснений, функция Int2Bits(x, n) определена во «Вспомогательные функции.mcd» и преобразует положительное целое число x в двоичный вектор длины n.

Nbit(r) := 2^r - 1 -- определение кол-ва битов n блочного кода (m, n), в который кодируются исходные по Хэммингу с числом контрольных битов r.

Mbit(r) := 2^r + r - 1 -- определение кол-ва битов m блочного кода (m, n), в который кодируются исходные по Хэммингу с числом контрольных битов r.

Vec2Matrix(v, m) -- преобразование двоичного вектора v в массив с числом строк m. Значения исходного вектора записываются в результирующий массив по-колонкам, количество результирующих колонок определяется размером вектора v. При необходимости последняя колонка дополняется нулями. Определение функции

Vec2Vecs(v, m) -- преобразование двоичного вектора v в вектор из векторов с числом элементов m. При необходимости последний вектор дополняется нулями. Определение функции

Matrix2Vec(M) -- преобразование матрицы M в вектор значений. Значения записываются по-столбцам. Определение функции

InitialCodes(str, r) -- переводит символы строки str в ASCI коды и преобразует их к двоичному представлению (8 бит на символ), полученный массив разделяет на блоки по m в соответствии со значением r. Возвращает матрицу из m строк, каждый из столбцов которой заполнен блоком из m бит, последний столбец может быть неполным (дополняется нулями). Определение функции

errCheckBlock(b, n, msg) -- вспомогательная функция контроля размера блока кода. Проверяет, что матрица b состоит из n строк, если это не так, то возвращается ошибка. Также проверяется, что блок содержит только нули и единицы. Определение функции

ExpandBlock(b, r) -- преобразует матрицу b из m строк в матрицу из Nbit(r) строк, вставляя в нее r строк (контрольных разрядов) на позициях 2ⁱ, где i = 0 .. (r - 1). Определение функции

BuildM(r) -- построение матрицы M для вычисления контрольных разрядов кода Хэмминга с числом контрольных разрядов r. Определение функции

AddControlCodes(b, r) -- заполнение контрольных битов кода Хэмминга в матрице b, число контрольных битов r. Определение функции

Codes2Str(codes) -- перевод матрицы кодов Хэмминга codes в строку символов. Определение функции

Str2HamingCodes(str, r) -- преобразование cтроки символов str в матрицу кодов Хэмминга с числом контрольных битов r. Определение функции

DetectErrors(b, r) -- обнаружение и корректировка ошибок в коде Хэмминга bk с числом контрольных разрядов r. Определение функции

HamBlock2Block(b, r) -- из массива кодов Хэмминга b выделяет исходный код (удаляет контрольные биты, r штук) и возвращает матрицу с исходными кодами. Определение функции

StrEncodeHam(str, r) -- кодирует символы строки str кодом Хэмминга с параметром r в ASCI коды и преобразует их к двоичному представлению (8 бит на символ), полученный массив разделяет на блоки по m в соответствии со значением r. Возвращает матрицу из m строк, каждый из столбцов которой заполнен блоком из m бит - кодом Хэмминга. Последний столбец может быть неполным (дополняется нулями). Определение функции

StrEncodeHam2Str(str, r) -- кодирует символы строки str кодом Хэмминга с параметром r в ASCI коды и преобразует их к двоичному представлению (8 бит на символ), полученный массив разделяет на блоки по m в соответствии со значением r, преобразует полученный код в строку символов. Возвращает строку символов. Длина строки больше, чем исходная строка из-за дополнительных разрядов. Определение функции

Описание функций построения матрицы для матричного кодирования Хэмминга

Кодирование Хэмминга может быть представлено матричной операцией:

b = Ea,

где a - двоичный вектор исходного блока кода; b - двоичный вектор блока кода Хэмминга; E - кодирующая матрица.

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

haBuildMatrix(r) -- строит матрицу M для вычисления контрольных разрядов. Старшие разряды - первые. Определение функции

haGetControlCols(M) -- вычисляет столбцы контрольных разрядов для матричного кодирования Хэмминга, используя матрицу M. Определение функции

haMakeE(r) -- возвращает кодирующую матрицу размером mn для кода Хэмминга с числом контрольных разрядов r. Определение функции

haEncode(b, r) -- кодирует блоки (колонки матрицы b) кодом Хэмминга с параметром r и возвращает закодированное в виде матрицы, где коды расположены в столбцах. Использует матричное кодирование (можно сравнить с ExpandBlock(b, r), BuildM(r), AddControlCodes(b, r)). Определение функции

haStrEncode(str, r) -- кодирует строку str кодом Хэмминга с параметром r и возвращает закодированное в виде матрицы, где коды расположены в столбцах. Использует матричное кодирование.

Размещено на Allbest.ru