Читайте также:
|
|
[убрать]
· 1 История
· 2 Систематические коды
· 3 Самоконтролирующиеся коды
· 4 Самокорректирующиеся коды
· 5 Код Хемминга
· 6 Литература
· 7 Применение
· 8 См. также
История[править | править исходный текст]
В середине 1940-х годов Ричард Хэмминг работал в знаменитых Bell Labs на счётной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машину с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и снова запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую.
Хэмминг часто работал в выходные дни, и все больше и больше раздражался, потому что часто был должен перезагружать свою программу из-за ненадежности перфокарт. На протяжении нескольких лет он проводил много времени над построением эффективных алгоритмов исправления ошибок. В 1950 году он опубликовал способ, который на сегодняшний день известен как код Хэмминга.
Систематические коды[править | править исходный текст]
Систематические коды образуют большую группу из блочных, разделимых кодов (в которых все символы можно разделить на проверочные и информационные). Особенностью систематических кодов является то, что проверочные символы образуются в результате линейных операций над информационными символами. Кроме того, любая разрешенная кодовая комбинация может быть получена в результате линейных операций над набором линейно независимых кодовых комбинаций.
Самоконтролирующиеся коды[править | править исходный текст]
Коды Хэмминга являются самоконтролирующимися кодами, то есть кодами, позволяющими автоматически обнаруживать ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.
При этом невозможно узнать, в каком именно разряде произошла ошибка, и, следовательно, нет возможности исправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, четырёх, и т.д. — в четном количестве разрядов. Впрочем, двойные, а тем более четырёхкратные ошибки полагаются маловероятными.
Самокорректирующиеся коды[править | править исходный текст]
Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенство или , где m — количество основных двоичных разрядов кодового слова. Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице.
Диапазон m | kmin |
2-4 | |
5-11 | |
12-26 | |
27-57 |
В настоящее время наибольший интерес представляют двоичные блочные корректирующие коды. При использовании таких кодов информация передаётся в виде блоков одинаковой длины и каждый блок кодируется и декодируется независимо друг от друга. Почти во всех блочных кодах символы можно разделить на информационные и проверочные. Таким образом, все комбинации кодов разделяются на разрешенные (для которых соотношение информационных и проверочных символов возможно) и запрещенные.
Основными характеристиками самокорректирующихся кодов являются:
1. Число разрешенных и запрещенных комбинаций. Если n - число символов в блоке, r - число проверочных символов в блоке, k - число информационных символов, то - число возможных кодовых комбинаций, - число разрешенных кодовых комбинаций, - число запрещенных комбинаций.
2. Избыточность кода. Величину называют избыточностью корректирующего кода.
3. Минимальное кодовое расстояние. Минимальным кодовым расстоянием d называется минимальное число искаженных символов, необходимое для перехода одной разрешенной комбинации в другую.
4. Число обнаруживаемых и исправляемых ошибок. Если g - количество ошибок, которое код способен исправить, то необходимо и достаточно, чтобы
5. Корректирующие возможности кодов.
Граница Плоткина даёт верхнюю границу кодового расстояния или при
Граница Хемминга устанавливает максимально возможное число разрешенных кодовых комбинаций где - число сочетаний из n элементов по i элементам. Отсюда можно получить выражение для оценки числа проверочных символов: Для значений разница между границей Хемминга и границей Плоткина невелика.
Граница Варшамова-Гильберта для больших n определяет нижнюю границу числа проверочных символов Все вышеперечисленные оценки дают представление о верхней границе d при фиксированных n и k или оценку снизу числа проверочных символов
Код Хемминга[править | править исходный текст]
Построение кодов Хемминга основано на принципе проверки на четность числа единичных символов: к последовательности добавляется элемент такой, чтобы число единичных символов в получившейся последовательности было четным. знак здесь означает сложение по модулю 2
. - ошибки нет, однократная ошибка. Такой код называется или . Первое число - количество элементов последовательности, второе - количество информационных символов. Для каждого числа проверочных символов существует классический код Хемминга с маркировкой т.е. - . При иных значениях k получается так называемый усеченных код, например международный телеграфный код МТК-2, у которого . Для него необходим код Хемминга , который является усеченным от классического . Для Примера рассмотрим классический код Хемминга . Сгруппируем проверочные символы следующим образом:
знак здесь означает сложение по модулю 2.
Получение кодового слова выглядит следующим образом:
=
На вход декодера поступает кодовое слово где штрихом помечены символы, которые могут исказиться в результате помехи. В декодере в режиме исправления ошибок строится последовательность синдромов:
называется синдромом последовательности.
Получение синдрома выглядит следующим образом:
=
Кодовые слова кода Хемминга
Синдром указывает на то, что в последовательности нет искажений. Каждому ненулевому синдрому соответствует определенная конфигурация ошибок, которая исправляется на этапе декодирования. Для кода в таблице указаны ненулевые синдромы и соответствующие им конфигурации ошибок (для вида: ).
Синдром | |||||||
Конфигурация ошибок | |||||||
Ошибка в символе |
Внимание мастеров маникюра и педикюра!
Дата добавления: 2014-12-19; просмотров: 39 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
ГО приема | | | Форматирование символа позволяет определить его основные параметры. |