Шпаргалка: Лекции по количественной оценке информации
при этом подразумевается, что общая длина кодовой комбинации
. (61)
Для практических расчетов при определении числа контрольных разрядов кодов с минимальным кодовым расстоянием удобно пользоваться выражениями:
(62)
если известна длина полной кодовой комбинации п, и
(63)
если при расчетах удобнее исходить из заданного числа информационных символов [10] .
Для кодов, обнаруживающих все трехкратные ошибки
(64)
или
(65)
Для кодов длиной в п символов, исправляющих одну или две ошибки
(66)
Для практических расчетов можно пользоваться выражением
(67)
Для кодов, исправляющих 3 ошибки
(68)
Для кодов, исправляющих s ошибок
(69)
Выражение слева известно как нижняя граница Хэмминга [16], а выражение справа – как верхняя граница Варшамова – Гильберта [3][11]
Для приближенных расчетов можно пользоваться выражением
(70)
Можно предположить, что значение будет приближаться к верхней границе в зависимости от того, насколько выражение под знаком логарифма приближается к целой степени двух.
Линейные групповые коды
Линейными называются коды, в которых проверочные символы представляют собой линейные комбинации информационных символов.
Для двоичных кодов в качестве линейной операции используют сложение по модулю 2.
Правила сложения по модулю 2 определяются следующими равенствами:
Последовательность нулей и единиц, принадлежащих данному коду, будем называть кодовым вектором.
Свойство линейных кодов: сумма (разность) кодовых векторов линейного кода дает вектор, принадлежащий данному коду.
Линейные коды образуют алгебраическую группу по отношению к операции сложения по модулю 2. В этом смысле они являются групповыми кодами.
Свойство группового кода: минимальное кодовое расстояние между кодовыми векторами группового кода равно минимальному весу ненулевых кодовых векторов.
Вес кодового вектора (кодовой комбинации) равен числу его ненулевых компонентов.
Расстояние между двумя кодовыми векторами равно весу вектора, полученного в результате сложения исходных векторов помодулю 2. Таким образом, для данного группового кода
.
Групповые коды удобно задавать матрицами, размерность которых определяется параметрами кода и . Число строк матрицы равно , число столбцов равно += :
(71)
Коды, порождаемые этими матрицами, известны как -коды, где , а соответствующие им матрицы называют порождающими, производящими, образующими.
Порождающая матрица С может быть представлена двумя матрицами И и П (информационной и проверочной). Число столбцов матрицы П равно , число столбцов матрицы И равно :
(72)
Теорией и практикой установлено, что в качестве матрицы И удобно брать единичную матрицу в канонической форме:
При выборе матрицы П исходят из следующих соображений:чем больше единиц в разрядах проверочной матрицы П, тем ближе соответствующий порождаемый код к оптимальному[12] , с другой стороны, число единиц в матрице П определяет число сумматоров по модулю 2 в шифраторе и дешифраторе, т. е. чем больше единиц в матрице П, тем сложнее аппаратура.
Вес каждой строки матрицы П должен быть не менее , где - вес соответствующей строки матрицы И. Если матрица И - единичная, то (удобство выбора в качестве матрицы И единичной матрицы очевидно: при усложнилось бы как построение кодов, так и их техническая реализация).
При соблюдении перечисленных условий любую порождающую матрицу группового кода можно привести к следующему виду: