0001010,...,1001000,1010000.
/* Коды,оптимальные с точки зрения избыточных символов,обнаруживающие максимально возможное количество вариантов ошибок кратностью
r + 1,r + 2 и имеющие d min < = 6 и n < = 40 были исследованы Д.
Слепяном.Для получения этих кодов подматрица Hp должна иметь комбинации с максимальным весом.Для этого при построении кодов с
d min = > 3 последовательно используются векторы длиной n - k = p
весом W = p, p - 1,p - 2,...,d min -1. */
Проверочные символы образуются за счёт линейных опнраций над информационными символами.Для каждой кодовой комбинации должно быть составлено p независимых сумм по модулю два.
Весьма удобно проверочные суммы составлять с помощью ПРОВЕРОЧНОЙ
МАТРИЦЫ H,которая строится следующим образом.В начале строится подматрица H1,являющаяся транспонированной по отношению к подматрице
Hp:
│b11 b21 ... bk1│
│b12 b22 ... bk2│
│ . . ... . │
H1 = │ . . ... . │.
│ . . ... . │
│b1p b2p ... bkp│
Затем к ней справа приписывается единичная матрица:
│b11 b21 ... bk1 1 0 0 ... 0 0│
│b12 b22 ... bk2 0 1 0 ... 0 0│
│ . . ... . . . . ... . .│
H = │ . . ... . . . . ... . .│.
│ . . ... . . . . ... . .│
│b1p b2p ... bkp 0 0 0 ... 0 1│
Алгоритм определения проверочных символов по информационным с помощью матрицы H следующий.Позиции,занимаемые единицами в первой строке подматрицы H1,определяют информационные разряды,которые должны учавствовать в формировании первого проверочного разряда кодовой комбинации.Позиции единиц во второй строке подматрицы H1 определяют информацмонные разряды,учавствующие в формировании второго проверочного разряда и т.д.
ПРИМЕР.Пусть производящая матрицакода P7,4 имеет вид:
│1 0 0 0 0 1 1│
│0 1 0 0 1 0 1│
P7,4 = │0 0 1 0 1 1 0│.
│0 0 0 1 1 1 1│
Проверочная подматрица:
│0 1 1│
│1 0 1│
Hp = │1 1 0│.
│1 1 1│
Транспонированная подматрица по отношению к Hp:
│0 1 1 1│
H1 = │1 0 1 1│.
│1 1 0 1│
Приписывая справа единичную матрицу,полуим проверочную матрицу:
│0 1 1 1 1 0 0│
H = │1 0 1 1 0 1 0│.
│1 1 0 1 0 0 1│
Кодовые комбинации должны содержать p = n - k = 7 - 4 = 3 проверочных символа.Подматрица H1 указывает на то,что проверочные символы должны опеделяться равенствами:
b1 = a2 + a3 + a4;
b2 = a1 + a3 + a4;
b3 = a1 + a2 + a4.
Тогда для сообщения,представляемого,например простой кодовой комбинацией 0011,проверочные символы будут:
b1 = 0 + 1 + 1 = 0;
b2 = 0 + 1 + 1 = 0;
b3 = 0 + 0 + 1 = 1.
Следовательно,полная кодовая комбинация будет иметь вид 0011001.
Проверочная матрица H очень удобна для определения места ошибки в кодовой комбинации,а следовательно,исправления ошибок.Проверка кодовых комбинаций при этом выполняется путём суммирования по модулю два проверочных символов кодовых комбинаций и проверочных символов, вычисленных по принятым информационным.В результате будет получена совокупность контрольных равенств,каждое из которых представляет сумму по модулю два одного из контрольных разрядов и определённого количества информационных.
Состав контрольных равенств легко определяется из проверочной матрицы H.В состав первого контрольного равенства должны входить символы,позиции которых заняты единицами в первой строке матрицы H.В
состав второго контрольного равенства должны входить символы,позиции которых заняты единицами во второй строке матрицы H и т.д.
Так,для рассмотренного ранее примера с кодом P7,4 эти равенства будут иметь вид:
S1 = b1 + a2 + a3 + a4;
S2 = b2 + a1 + a3 + a4;
S3 = b3 + a1 + a2 + a4.
В результате p таких проверок будет получено p - разрядное двоичное число S ( СИНДРОМ ),которое будет равно нулю при отсутствии ошибок и отлично от нуля в случае наличия ошибок ( определённой кратности!).
Если код предназначен для ИСПРАВЛЕНИЯ ОШИБОК,то должно быть заранее определено СООТВЕТСТВИЕ между ВИДОМ СИНДРОМА И ВИДОМ ИСПРАВЛЯЕМОЙ ОШИБКИ.
Пусть в рассмотренном примере P7,4 с проверочной матрицей H
│0 1 1 1 1 0 0│
H = │1 0 1 1 0 1 0│.
│1 1 0 1 0 0 1│
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.