2014-02-12
2217
Код Хэмминга
Совершенные коды
Известно всего два совершенных кода. Это код Хэмминга и код Голея (12, 24), исправляющий 8 ошибок на блок. Более точно, код Хэмминга — это группа совершенных кодов с dmin = 3.
Коды Хемминга —линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку на блок.
Достоинство кода в том, что реализация алгоритма требует небольших ресурсов и может быть выполнена аппаратно.
Исходными данными для кодирования является произвольная двоичная последовательность, например как это изображено на рис. 16
Исходная битовая последовательность
| № бита | … | n | |||||||||||||||||||||
| значение бита |
Рис. 16.
Прежде всего, двоичная последовательность делится на блоки размером в n бит. Размер исходных блоков не произволен, их длина определяются формулой
n = 2r ‑ r - 1,
|
|
|
где r – любое целое число, большее 2. Эти блоки будем называть «блоки исходного кода» и обозначать ai.
Положим для определенности r = 4, тогда n = 11. Блоки исходного кода изображены на рис. 17.
Разделение битовой последовательности на блоки исходного кода
Рис. 17.
Далее исходные коды расширяют до m бит каждый, дополняя r контрольными битами. Полученные m-битные коды образуются так:
· Позиции с номерами 2i (i = 1, 2, …r) резервируются под контрольные биты;
· в остальные биты копируется исходный код в порядке следования его битов.
Расширенные блоки будем называть «блок кода» и обозначать bi. Расширение исходного кода для r = 4 и n = 15 продемонстрировано на рис. 18.
Расширение блоков исходного кода контрольными разрядами
|
Рис. 18
Затем вычисляют контрольные разряды. Для вычисления нужна вспомогательная матрица M размером (2r – 1) строк и r столбцов. Матрица заполняется по строкам, в каждую строку записывают двоичное представление чисел от 1 до 2r – 1, младшие биты пишут ПЕРВЫМИ. Такая матрица для r = 4 показана на рис. 19. Далее вычисляются контрольные разряды ci, для этого из матрицы M выбираются и побитно суммируются все строки, номера которых совпадают с номерами ненулевых бит блока кода bi. Полученная строка из r битов записывается в контрольные разряды блока кода bi в порядке следования битов, как показано на рис.19.
|
|
|
Вычисление контрольных разрядов ci можно представить матричным умножением
ci = (bi)T×M,
здесь (bi)T — строка-блок расширенного кода, где контрольные биты равны 0.
Блоки кода можно вновь преобразовать в последовательность бит и передавать по каналу связи.
Код Хемминга способен детектировать и исправлять 1 (одну) ошибку на блок.
Вычисление контрольных разрядов
Рис. 19.
