Главная страница  Дискретный канал связи 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [ 21 ] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

1110 0 10 0 10 110 0 1

Очевидно, что ценность стандартного расположения относительна. Для больших пик составлять такую таблицу было бы не практично.

Таблицу можно упростить, если мы сможем помнить только первый столбец и находить остальные столбцы по мере необходимости. Это можно сделать, введя понятие синдрома ошибок.

Для любого принятого вектора v определим синдром равенством

S = vH.

Теорема 3.3.1. Все векторы из одного смежного класса имеют одинаковый синдром, присуший только этому смежному классу.

Доказательство. Если v и v лежат в одном смежном классе, то V = Сг -Ь у, v = c + у для некоторого у и кодовых слов Cj и Cj Для любого кодового слова с выполняется равенство сН = 0. Отсюда получаем

S = vH = уН\

s = vнт = yн

и, следовательно, s = s. Обратно, допустим, что s = s, тогда (v - v) Hf = О, и поэтому разность v - v является кодовым словом. Следовательно, v и v принадлежат одному смежному классу. □

Любые два вектора из одного смежного класса имеют одинаковый синдром. Следовательно, нам необходимо только свести в таблицу синдромы и лидеры смежных классов. Затем мы можем производить декодирование следующим образом. По принятому вектору V вычисляем синдром и находим соответствующий этому синдрому лидер смежного класса. Этот лидер является разностью между принятым словом и кодовым словом, которое одновременно является центром сферы кодирования. Таким образом, мы исправим ошибку, вычтя из слова v лидер смежного класса.

В примере, приведенном выше, проверочной матрицей будет



й новая таблица запишется в виде

i.i. коды ХЭММИНГА 71

Лийеры

смежных.

классов

Синйромы

0 0 0 0 0

0 0 0 0 1

0 0 1

0 0 0 10

0 1 0

0 0 10 0

1 0 0

0 10 0 0

1 0 1

10 0 0 0.

1 1 1

0 0 0 11

0 1 1

0 0 110

1 1 0

Эта таблица проще, чем стандартное расположение. Предположим, что принят вектор v = 10010. Тогда s = vH = 101. Лидер смежного класса будет равен 01000. Отсюда получим, что переданное слово равно 10010 -01000 = 11010, а информационное слово равно 11.

3.4. КОДЫ ХЭММИНГА

Код, у которого минимальное расстояние не менее трех, в силу следствия 3.2.3 имеет проверочную матрицу, в которой все столбцы ненулевые и различные. Если проверочная матрица двоичного кода имеет т строк, то каждый столбец оказывается двоичным числом длины т. Существует всего 2™ - 1 возможных столбцов. Следовательно, если Н -матрица двоичного кода с d* 3- имеет /п строк, то она может иметь не более 2" - 1 столбцов. В результате получается (2" - 1, 2" - 1 -т)-код. Простейший нетривиальный пример соответствует m = 3. В этом случае матрицы Н и G в систематическом виде запишутся следующим образом:

110 110 0 10 110 10 0 1110 0 1

1 0 0 0 1 1 0

0 10 0 10 1

0 0 1 0 0 11

0 0 0 1 1 1 1



Gf(2)

Gf(4)

Gf(8)

GF(16)

Gf(27)

(7. 4)

(5, 3)

(9,7)

(17, 15)

(28, 26)

(15.11)

(21, 18)

(73. 70)

(273, 270)

(757, 754)

(31,26)

(85,81)

(585, 581)

(6Х 57)

(341, 336)

(127, 120)

Например (13,10)-код Хэмминга над GF (3) задается проверочной матрицей

1 1 1 1 1 1 I 1 О О 1 О о 00111222110 10 .1201201212001

Такие (2" - 1, 2" - 1 - т)-коды называются кодами Хэм» минга.

Ясно, что каждая пара столбцов матрицы Н линейно независима (поскольку никакая пара различных двоичных векторов не дает в сумме нуля), а некоторые множества из трех столбцов будут линейно зависимы. Следовательно, согласно теореме 3.2.2, минимальный вес кода равен 3 и код исправляет одиночные ошибки.

Определение кодов Хэмминга легко обобщить на случай больших алфавитов. Достаточно просто заметить, что главная идея построения таких кодов состоит в определении матрицы Н, любая пара столбцов которой линейно независима. Для задания проверочной матрицы нельзя использовать все ненулевые т-последо-вательности над GF (q), q Ф 2, поскольку некоторые из них попарно линейно зависимы. Чтобы обеспечить линейную независимость, выберем в качестве столбцов матрицы все т-последовательности, у которых первая ненулевая компонента равна единице. Тогда все столбцы будут попарно линейно независимыми, а некоторые тройки столбцов могут оказаться линейно зависимыми, и минимальный вес в коде будет равен трем.

Всего существует (q" -\)l{q - 1) таких различных столбцов. Следовательно, .получившийся код будет {{q" - \)l{q-1), (qin - lyiq - 1)~ т)-кодом. Код Хэмминга, исправляющий одиночные ошибки, существует для каждого q, для которого существует поле GF (q), и для любого т. Для примера в табл. 3.1 приведены параметры нескольких кодов Хэмминга.

Таблица 3.1

Параметры (я, ft) некоторых кодов Хэмминга




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [ 21 ] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

0.0094