Телеграфные службы. Службы ПД. Защита от ошибок и преобразование сигналов. Факсимильные службы. Единая система документальной электросвязи, страница 8

Код Хемминга. Рассмотрим в качестве примера построение систематического кода с кодовым расстоянием do= 3 (кода Хемминга). Пусть число сообщений, которое необходимо пе­редать, равно 16. Тогда необходимое число информационных элементов k = log₂N_a = 4. Можно выписать все 16 кодовых комбинаций, включая нулевую (0000). Это один из возможных способов задания исходного (простого) кода. Другой способ заключается в выписывании только четырех кодовых ком­бинаций простого кода в виде матрицы, называемой еди­ничной:

Суммируя по модулю два в различном сочетании кодовые комбинации, входящие в единичную матрицу, можно получить 15 кодовых комбинаций, 16-я — нулевая. Кодовые ком­бинации, составляющие матрицу (12.1), линейно независимы. Можно было бы составить матрицу и из других кодовых комбинаций (лишь бы они были линейно независимыми). Ненулевые комбинации А₁, А₂, Л₃, А₄ линейно независимые, если q₁A₁ q₂A₂ q₃А₃  q₄A₄ ≠ 0, где qi {0,1} при условии, что хотя бы один из коэффициентовqi ≠ 0. До­полним каждую кодовую комбинацию в (12.1) проверочными элементами так, чтобы обеспечивалось do= 3. Будем иметь в виду также тот факт, что к числу разрешенных комбинаций корректирующего кода принадлежит и комбинация 0000 ... 0,

называемая нулевой. Очевидно, что в числе добавляемых про­верочных элементов должно быть не менее двух единиц. Тогда общее число единиц в каждой комбинации кода получим не меньше трех и комбинации, полученные нами, будут отличать­ся от нулевой, по крайней мере, в трех элементах. Добавим по две единицы к каждой строке матрицы (12.1):

видим, что они отличаются только в двух элементах, т.е. заданное кодовое расстояние не обеспечивается. Дополним каждую строку проверочными элементами так, чтобы do= 3.

Тогда матрица примет вид

Добавляемые проверочные элементы могут быть записаны и в другом порядке. Необходимо лишь обеспечить do= 3.

Матрицу (12.3) называют производящей, или порождающей, матрицей кода (7,4), содержащего семь элементов, из которых четыре информационных. Обычно матрицу обозначают буквой G с индексом, указывающим, к какому коду она относится (в нашем случае G_(7,4)). Производящая матрица состоит из двух матриц — единичной (размерности k• k) и С_(r,k) , содержащей r столбцов и kстрок. Суммируя в различном сочетании строки матрицы (12.3), получаем все (кроме нулевой) комбинации корректирующего кода с do= 3.