Коды Хэмминга — вероятно, наиболее известный из первых
самоконтролирующихся и самокорректирующихся
кодов. Построены они применительно к
двоичной системе счисления.
Одними из самых простых
являются коды Хэмминга, представленные Хэммингом
в 1950г.
К данным кодам относятся линейные блоковые
коды с параметрами (n,k) вида (2m—
1, 2m -т — 1), где т=п — число проверочных символов кода.
- Коды Хэмминга обладают кодовым расстоянием dmin=3 и поэтому способны исправлять только одну или обнаружить две ошибки.
- Для задания кодов Хэмминга обычно используется проверочная матрица Н, содержащая и строк и 2m -1 столбцов, причем столбцами являются все возможные ненулевые двоичные векторы длины m.
- Порождающая матрица даннаго кода формируется из единичной матрицы размером К*К и транспортированной подматрицы, состоящей из первых К строк матрицы Н:
- Коды Хэмминга являются одними из немногих кодов, для которых полностью известно распределение весов кодовых слов, определяемое весомой функцией
Коды Хэмминга являются самоконтролирующимися кодами, то есть кодами, позволяющими
автоматически обнаруживать ошибки при
передаче данных.
Для
их построения достаточно приписать к
каждому слову один добавочный (контрольный)
двоичный разряд и выбрать цифру этого
разряда так, чтобы общее количество единиц
в изображении любого числа было, например,
четным.
- Одиночная ошибка в каком-либо разряде передаваемого слова изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.
- При этом невозможно узнать, в каком именно разряде произошла ошибка, и, следовательно, нет возможности исправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, четырёх, и т.д. — в четном количестве разрядов. Впрочем, двойные, а тем более четырёхкратные ошибки полагаются маловероятными.
Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося
кода, рассчитанного на исправление одиночных
ошибок, одного контрольного разряда недостаточно.
Корректирующие
коды
- В настоящее время наибольший интерес представляют двоичные блочные корректирующие коды. При использовании таких кодов информация передаётся в виде блоков одинаковой длины и каждый блок кодируется и декодируется независимо друг от друга. Почти во всех блочных кодах символы можно разделить на информационные и проверочные. Таким образом, все комбинации кодов разделяются на разрешенные (для которых соотношение информационных и проверочных символов возможно) и запрещенные.
Укороченные
и расширенные коды
- Укороченные коды Хэмминга получаются при исключении какой-либо проверки (т.е. удалении одной строки проверочной матрицы). Расширенные коды Хэмминга получаются путем введения дополнительной проверки на четность всех символов кодового слова. В результате их минимальное расстояние увеличивается до Dmin=4, что позволяет данным кодам исправлять одну обнаруживать две или только обнаруживать три ошибки.
Представлены экспериментальные
зависимости вероятности битовой ошибки
Рb от вероятности ошибки в канале р и от
отношения сигнал-шум на бит Еb / N0 для кодов Хэмминга с т=З — 7 при
работе в ДСК, декодируемых с помешаю текст не целый!!!!
Далее рассмотрим характеристики кодов Хэмминга.
Заметим, что между
вероятностью ошибки р в канале
и отношением сигнал- шум на бит Еb/N0 существует
следующая зависимость:
Где:
- Q(x) — функция, определенная ;
- r — кодовая скорость кода (r=kln).
- Как видно из представленных рисунков, коды Хэмминга обладают очень слабой корректирующей способностью и отдельно практически не используются. Однако применение данных кодов в составе каскадных схем кодирования (например, Turbo Product Codes ) позволяет получить очень хорошие результаты.