Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 70
Текст из файла (страница 70)
Схема вычисления синдрома Рис.7.4. Схема кодера различных смежных классов синдромы различны. Поэтому с каждым смежным классом можно сопоставить один, и только один синдром. Оптимальное декодирование в 2СК без памяти можно тогда производить, отыскивая слово минимального веса, синдром которого совпадает с синдромом, полученным по принятому слову.
Такой алгоритм декодирования называется синдромным, Табличный способ синдромного декодирования состоит в запоминании таблицы, связывающей различные синдромы с лидерами соответствующих им смежных классов. Схемы кодирования и вычисления синдрома для произвольного линейного кода приведены на рис. 7.4 и рис. 7.5. Элемент порождающей матрицы рд определяет характер связи г-й ячейки регистра с ~'-м сумматором: если р; = 1— связь есть, если р; = Π— связь отсутствует.
Кодирование происходит следующим образом: вектор Ь записывается в регистр, после чего с выходов сумматоров считывается вектор с. Для кодирования систематического кода необходимо лишь п — 1г сумматоров, связи которых с регистром задаются матрицей Р.
При этом вектор х образуется из вектора Ь и выходов и — 1г сумматоров (вектора с). На рис. 7.5 элемент проверочной матрицы Ь„определяет характер связи г'-й ячейки регистра с 7'-м сумматором: если 1з, =1 — связь есть, если Ьсз = Π— связь отсутствует. Для вычисления синдрома вектор у записывается в регистр, после чего с выходов сумматоров считывается з.
При использовании линейных кодов выраженная числом двоичных сложений сложность процедуры кодирования и процедуры вычисления синдрома (декодирование с обнаружением ошибок) не превышает и'. Это значительно меньше, чем при табличном кодировании и декодировании. Для конкретизации алгоритма декодирования с исправлением ошибок учтем, что принятый вектор у можно записать в виде у= х®е, где е — вектор ошибок в канале (размерностью и ). Если конкретная реализация е имеет вес го (го ненулевых компонент) и в меньше г„для заданного кода, то ошибки в у могут быть исправлены. Вектор е входит в выражение для синдрома (7.5б), и с учетом (7.54) В=уН =хН +еН =еН . Вероятность р правильного декодирования кодового слова в любом канале связи при использовании табличного способа синдромного декодирования (по алгоритму максимального правдоподобия) будет определяться следующим соотношением: 279 2 -1 Р = ~Р(е=$1), (7,58) 1О где яо — означает нулевое слово, и, следовательно, Р(е = яо) соответствует вероятности безошибочного приема кодового слова.
(Очевидно, что р, = 1 — р ь Для 2СК без памяти стандартное расположение дает правило декодирования по максимуму правдоподобия, если каждый лидер выбирается как слово минимального веса в своем смежном классе. Тогда для вероятности правильного декодирования получаем следующую точную формулу р = Хр ('-р)" (7.59) 1-О где о»1 — минимальный вес слова в 1-м смежном классе. К сожалению, использование (7.59) для мощных кодов оказывается затруднительным, поскольку требует построения необходимой таблицы стандартного расположения или знания так называемого спектра смежных «лассов, т.е. распределения весов Хзмминга для слов, входящих в каждый из смежных классов кода, что удаатся сделать лишь для некоторых частных случаев.
Соотношение (7.59) показывает„что некоторый (л, 7о)-код будет оптимальным в 2СК без памяти, т.е. обеспечит максимальную величину р, если все его лидеры минимального веса совпадут с набором образцов ошибок от 0 до некоторой кратности ь Поскольку полное число о таких образцов ошибок равно ~~с, а число смежных классов равно 2 ", то зто требует вы- 1-О полнения условия г"-» = ~с„', (7.60) 1О где г — некоторое целое число. Очевидно, соотношение (7.60) выполняется не для всех (л, «)-кодов. Напротив, его выполнение — зто редчайший случай. Коды, которые удовлетворяют атому условию, называются совершенными.
Известно лишь два нетривиальных двоичных (л, й)-кода с параметрами, удовлетворяющими (7.60), — это код Хэмминга и код Голея (23,12). (Они будут определены несколько позже.) Максимум в (7.59) может обеспечить и так называемый «вазисовершенный код, среди образующих смежных классов которого при некотором г содержатся все последовательности веса ~ или меньше, часть последовательностей веса Г+ 1 и нет ни одной последовательности большого веса. К сожалению, квазисовершенные коды также встречаются достаточно редко.
Даже если некоторый линейный код имеет известное значение а', расчет рн (1') или р д($') в 2СК без памяти по границам (7.38), (7.41) или (7.43) может привести к достаточно грубым оценкам. Это особенно относится к расчету обнаруживающей способности кода для больших вероятностей ошибок р. Поскольку для линейных кодов необнаруженная ошибка происходит тогда, и только тогда, когда образец ошибки совпадает с одним из ненулевых кодовых слов, то можно привести точную формулу для расчета р„„(Р) в 2СК без памяти: р (1') =~У,р'(1 — р) (7.61) 1 Ф где Ф; — число слов кода веса», т.е. так называемый весовой спектр кода. Если, в частности, положить в (7.61) р = 1/2, то для любого (л, Ф) кода по- 2 — 1 И лучаем р = — „, что, как правило, значительно меньше, чем — „~~~„С„', полу- 2 чаемую по (7.38) для этого же значения вероятности ошибки символа в канале связи.
(Заметим, что ситуация, соответствующая случаю "обрыва канала", является отнюдь не бессмысленной для обнаружения ошибок, поскольку канал 280 может лишь временно перейти в состояние обрыва и мы должны обеспечить практическое отсутствие ошибок у получателя и в таком состоянии.) (7.63) где А, = ~Ч,Ц (бу), М, (~',/) = ~1 С~+;~ 'С (7,65) е ~-и г пьах(об-~) Если для данного кода Р'в 2СК без памяти для любых р, 0 < р < 1 выполняется неравен- ство р„(1, 1„, р) Я р (1, 1„, 1/2) = „, ~С„', ю О то он называется г — хорошим кодам.
(Сушествуют необходимые и достаточные условия, при которых код оказывается г — хорошим, но они также требуют знания спектра кода. Если (л, lс)-код г с известным спектром (Лз) используется для исправления ошибок по максимуму правдоподобия, а не толъко гаран~д-П тированной кратности до ~ — ~, то роз(Р') будет иметь следующую верхнюю границу, которую легко вывести, используя аддитивную верхнюю границу: р„<~„,У, ',~ Сзр (1-р)"'. л б ~л+11 (7.66) Если нас интересует не безошибочная передача всего сообщения, а среднее число ошибочных информационных символов после декодирования, то в общем случае это требует весьма громоздких расчетов.
При малой вероятности ошибки символа для средней битовой ошибки рь получено для симметричного канала без памяти приближенное выражение [131 281 Можно доказать, что при любой вероятности ошибки р, о яр к 1/2 в 2СК (это верно и для любых двоичных каналов с памятью) существует такой (л, й)-код Р; что ()- —,, 1 (7.62) Однако не обязательно для всех (л, й) наборов существует один и тот же (л, /с)-код, кото- рый обеспечивает выполнение (7.62) для всех 0<ря172. Если такой код существует, то он называется хорошим кодом. Неравенство (7.62) может быть обеспечено в любом канале связи, если (л, /с)-код используется совместно со стохосшическими преобразованиями канала на пе- редаче и приеме.
Эти преобразования сохраняют вероятности безошибочного приема л-блока и делают равновероятными все другие образцы ошибок. Однако такой подход требует обеспе- чения синхронизации между приемом и передачей для выполнения взаимообратных преобра- зований, что делает их в действительности псевдослучайными.
Известные спектры имеют достаточно редкие классы линейных кодов, однако часто уда- ется в точности рассчитать зтн спектры путем перебора всех 2" комбинаций данного )' кода или 2" " комбинаций дуалъного к нему кода. Действительно, согласно лемме Мак Вильяма 12Ц р„,(Р') может бъггь рассчитана по спектру дуалъного кода М, следуюшим образом: и р,„(и)= 2ь "~ М,(1 — 2р) — (1 — р) ! б где ы — минимальное расстояние для дуалъного кода И „М, — спектр дуального кода. Если (л, к)-код г' используется для совместного исправления ошибок кратности до г„и обнаружения ошибок в соответствии с определением 9, то р (Р'А„)= ~А, р~(1-р) (7.64) / б-и длины. Данный класс кодов может быть определен также иначе, как совокупность выходных последовательностей при различных начальных заполнениях линейного регистра длины в со связями,' выбранными так, чтобы период выходной последовательности оказался равным 2' — 1.
Поэтому они получили название последовательностей максимальной длины или М-последовательностей. Все комбинации данного кода, кроме нулевой, имеют одинаковый вес 2' ' и, следовательно, для такого кода д = 2 '. Коды Хэмминга и М- последовательности являются крайними случаями кодов с малой и большой величиной минимального кодового расстояния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
