Теория информации

сложения, 3aMKHjrrocTb группы означает, «гго при сложении двух элементов группы получается элемент, принадлежащий этой же ipynne. В качестве опера­ ции сложения используется поразрядное сложение по модулю 2 (так как число разрядов у кодов не должно увеличиваться при вьпюлиении операции сложе­ ния). Дня построения кода, способного обнаруживать и исправлять одиночную ошибку, необходимое число контрольных разрядов будет составлять « - A> l o g ( « + 1), где А - число разрядов исходной кодовой комбинации, п - число разрядов после добавления контрольных символов, г - число котрольных символов. Если не­ обходимо иметь возможность исправлять однократные и двукратные ошибки, то число контрольных разрядов определяется неравенством «-&>log (l +c ' + С„'). В общем случае, число контрольных символов определяется неравенст­ вом Хэммнн]~а п-к> i o g ( i + с ч С.' +...+с;) =l o g ^ c ; , где / - максимальное число одновременно исправляемых ошибок. 6.4. Коды Хэмминга Код Хэлшинга является фупповым («, Л)-кодом с минимальным расстоя­ нием D = 3, который позволяет обнаруживать и исправлять однократные ошиб­ ки. Для построения кода Хэмминга используется порождающая матрица, кото­ рая имеет вид ~ {^ЬЦП-К)^К)' где —матрица двоичилх элементов; - единичная матрица; к - число информационных разрядов кода; п - общее число разрядов кода. Порождающей матрице соответствует проверочная матрица Мшрица Aio<t,^) соддзжит к строк, представляющих все возможные двоичные комбинации длины п - А с не менее чем двумя единицами. Например, (7, 4)-код Хэмминга из табл. 6.3 имеет следуюпдае порождшощую и проверочную матрицы: 1 0 1 0 0 0^ 0 1 1 0 1 0 0 1 1 1 0 0 1 0 J О 1 О О О 78 =