Главная Помехоустойчивое кодирование



числа Vy то правильные значения Q в кодовом слове {Q . • Q} из и символов встречаются чаще.

Недостаток и-кратного повторения - большая избыточность при передаче сообщения. Однако основная идея, лежащая в основе возможности коррекции ошибки, наглядно иллюстрируется; используемый кодовый набор должен состоять из слов, отличающихся в п = 2у+ 1 числе символов. Здесь мы приходим к важному количественному показателю, характеризующему помехоустойчивость, - минимальному кодовому расстоянию, рассматриваемому ниже.

Основной путь повышения помехоустойчивости (за счет избыточности) - не /7-кратное повторение, а расширение сообщения (2 =

-i путем введения дополнительных символов р, называемых контрольными или проверочными и связанных с информационными символами [Of той или иной функциональной зависимостью.

Блоковые и неблоковые коды. Разобьем информационную последовательность {Qi, Q2> • • 1 на блоки Q длины к и введем в них по т проверочных символов ру е К. Переход от информационных символов к подобной расширенной совокупности символов называется избыточным кодированием.

Возможны две укрупненные стратегии выбора проверочных символов в процессе избыточного кодирования: 1) символы pj связывают не только с информационными символами этого блока, но и с предьщу-щей последовательностью из других блоков; 2) символы pj для некоторого блока Q определяют лишь по к информационным символам данного блока: ру = f(Q)i где fj - произвольные функции от к аргументов {б/ j .

В первом случае говорят о последовательном (неблоковом) кодировании; соответствующий последовательный код характеризуется Памятью, учитывающей влияние не только текущего блока, но и других предшествующих ему по времени блоков.

Во втором, более простом, случае набор из /? = А: + m (к информационных и т проверочных) символов называется кодовым словом, а совокупность всех возможных кодовых слов - блоковым кодом.

В настоящее время наибольшее распространение получили блоковые коды, которые и рассматриваются далее.

Условимся информационные символы внутри блока Q нумеровать

справа налево: Q= (QkQk-i-- .GOwG/ = 1, 2,1.

Так как lA"! = q, то количество кодовых слов блокового кода (его мощность) совпадает с числом сообщений - которые можно

составить с помощью блока Q длины к из символов G К.

До сих пор для простоты предполагалось, что информационные символы входят в каждое кодовое слово в неизменном виде, а их положение фиксировано; например, информационные символы расположены в начале кодового слова, а проверочные - приписываются к ним справа. Такие блоковые коды называются систематическими.



в принципе возможен вариант, когда все п символов, а не только проверочные, кодового слова W ~ (w,jWj j . . .vvi) являются некоторыми функциями от к информационных символов:

i =F-{Q), i = 1, 2,..., /7.

(1.1)

Все множество {F возможных функций в формуле (1.1) распадается на два класса линейных и нелинейных функций; соответственно с этим блоковые коды делятся на линейные и нелинейные.

Итак, переход QW от сообщения Q т к информационных символов к кодовому слову W длины п называется блоковым кодированием, а совокупность {W } всех таких кодовых слов, т. е. наборов W = (w„, .. . , Wi) длины w, - блоковым кодом. Мощности блокового кода и множества сообщений совпадают: IIV}

Отношение к/п принято называть скоростью, п - Длиной, а А: - размерностью блокового кода.

Минимальное кодовое рассто5шие. Количество ненулевых компонент кодового слова W называется его весом и обозначается wt(), а число позиций, в которых различаются два кодовых слова ~ W ~ (w, 1, • • • ) ) и " = (w, w J, . . . , ), называются (кодовым) расстоянием и обозначаются dist(, W"). Например, wt(0213) = 3, wt(llOll) = 4; dist[(0213), (1233)] = 2, dist[(01101), (11011)] = = 3.

Зададимся парой двоичных кодовых слов W и W". Пересечением W *W" двух двоичных слов длины п называется слово такой же длины п, координаты которого равны покомпонентным произведениям соответствующих координат исходных слов, т. е.

W *W (w„w„, w„ iW„ j,...,WiWi ), (1.2)

где Wjw" - обычное арифметическое произведение элементов из множества (0,1}, Z = 1, 2, ..., /7. Например, (10110) * (10011) - (10010).

Минимальным кодовым расстоянием d блокового кода называется минимальное расстояние между любой парой его кодовых слов:

c? = min dist(/, W,),

гц,е минимум берется по всем парам {Wj, Wj ) кодовых слов.

Таким образом, любые два слова блокового кода с минимальным расстоянием d различаются по крайней мере в d позициях.

Если блоковый код линеен, то его кодовое расстояние может быть определено также по весу ненулевых кодовых слов:

c? = min wt(,), ФО,

где минимум берется по всем ненулевым словам блокового кода



Возможность контролировать ошибки - обнаруживать (без исправления) или исправлять их с помощью того или иного кода - определяется его минимальным кодовым расстоянием [49].

Утверждение 1.1. Код с минимальным кодовым расстоянием d позволяет обнаруживать d - 1 ошибок или одновоеменно испшвлять

ошибок

c?>2u + r+ 1.

(1.3)

Таким образом, код с минимальным расстоянием d позволяет исправить либо г == с? - 1 стираний, либо v = int (0,5 (d ~ 1)} ошибок; наконец, если d - четное число, то можно не только исправить 0,5 (d - 2), но и одновременно обнаружить 0,5 d ошибок.

Выше использовалась малая Антье-функция intlA}, равная ближайшему целому числу, не большему N. Заметим, что далее также используется большая Анье-функция INT {л }, равная ближайшему целому числу, не меньшему N.

Как уже отмечалось, мощность множества сообщений {q} блокового кода длины к равна qk т. е. оно состоит из всевозможных сообщений Q = {Qj, Qk-i • • Ql) w Qi = (о, 1, ..., - i) .

Ясно, что в зтом множестве всегда найдутся пары кодовых слов, различающихся всего в одном разряде. Таким образом, минимальное кодовое расстояние подобного безызбыточного кода, образованного множеством сообщений { Q}-, равно 1 и из формулы (1.3) следует, что он не способен контролировать ошибки {т = и = О) . Вот почему для обеспечения помехоустойчивости используются избыточные коды.

Более подробные сведения по затронутым здесь вопросам можно найти в работах [8, 11, 15, 20, 22, 29, 30, 36, 40, 43].

1.2. АЛГЕБРАИЧЕСКОЕ КОДИРОВАНИЕ - ДЕКОДИРОВАНИЕ

БЛОКОВЫХ КОДОВ В БЕСКОНЕЧНОМ ПОЛЕ

Общие соображения. До сих пор мы говорили о дискретных сообщениях, информационные символы которых принадлежали к некоторому конечному множеству К. Для того чтобы можно было обрабатывать символы Qj, не выходя за пределы множества К, т.е. чтобы промежуточные и конечные результаты вычислений также принадлежали этому множеству, необходимо использовать специальную алгебру с особыми операциями, отличающимися от традиционных

"школьных" операций. Другими словами, целесообразно использовать такой конечный алфавит К, над злементами ("буквами") которого можно производить все четыре арифметические действия: сложение, вычитание, умножение и деление.



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


0.0128