Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 67
Текст из файла (страница 67)
Такие классы кодов рассматриваются в следующем разделе. 7.3.2. КОДЫ С ГАРАНТИРОВАННЫМ ОБНАРУЖЕНИЕМ И ИСПРАВЛЕНИЕМ ОШИБОК Пусть задан некоторый блоковый код длины и, состоящий из М комбинаций (блоков, слов, векторов) хь х2, ..., ху. Для упрощения определений и доказательств будем всюду считать, что входной Хи выходной г алфавиты канала совпадают. В общем случае канал может иметь память и задаваться вероятностями р(х~у) переходов входных блоков х в выходные у. Определение 1.
Расстоянием Хзмминга р(х,х') между двумя комбинациями х нХ" и х' нХ" будем называть число позиций этих комбинаций, в которых отдельные кодовые символы х и х' не совпадают. Очевидно, что 1< р(х,х')<п для любых х'~х и что р(х,х) = 0 для любых х нХ". Определение 2.
Образцом ошибки е будем называть двоичный блок длины и, который имеет единицы в тех позициях, в которых символы переданного х и принятого у блоков отличаются друг от друга, и нули — в остальных позициях. Ранее в гл. 2 были сформулированы аксиомы, которым должно удовлетворять абстрактное определение понятия расстояния в функциональных пространствах сигналов.
Покажем, что расстояние Хэмминга удовлетворяет этим аксиомам на пространстве т-ичных последовательностей произвольной длины ж Первые требования: р(х,у)>О,р(х,х)=О,р(х,у)=р(у,х) удовлетворяются очевидным образом. Остается проверить лишь справедливость "неравенства треугольника": р(х,у) < р(х,х)+ р(у,х) . (7.30) Предположим, что х и х отличаются друг от друга в позициях й, ч, ..., ~,, где з, = р(х,х), а у и х — в позициях ~',, у', ..., у„, где з = р(у,х). Тогда легко убедиться, что х и у не могут различаться в каких-либо позициях, отличных от (~, л,, ~', ., у', ), а если ч = 7,, то в этой позиции они могут и совпадать.
Поэтому р(*,у) < з, +зз, что и эквивалентно неравенству (7.30). Определение 3. Весом Хэмминга ~х~ блока (вектора) х (аналогично для у и е) будем называть число ненулевых символов этих блоков. Определение 4. Краткостью образца ошибки е (или короче — кратностью ошибки) будем называть его вес Хэмминга ~е~. (По существу это число ошибок, которое произошло при передаче блока х.) Декодирование в заданном канале связи по максимуму правдоподобия — это принятие решения о передаче такого кодового блока х,. еР, для которого условная вероятность Р(у~х,) максимальна, где у — принятый блок.
Это правило получения оценки можно записать в следующей компактной форме: 268 х, = Агашах Р(у(х,). (7.31) Как понятно из гл. 5, такое правило' приводит к максимально возможной средней вероятности правильного приема кодовых блоков при равновероятной посылке этих блоков по каналу связи. (Если последнее условие не выполняется, то оптимальное декодирование должно соответствовать правилу максимальной апостериорной вероятности.) Определение 5. Декодированием по минимуму расстояния Хэмминга будем называть следующее правило (алгоритм) принятия решения: х, =А к впр(у,х,). (7.32) (По существу, правило (7.32) означает, что считается переданной та кодовая комбинация, которая отличается от принятой в наименьшем числе позиций.) Покажем, что для тСК без памяти правила (7.31) и (7.32) совпадают, т.е.
декодирование по минимуму расстояния Хэмминга совпадает с декодированием по максимуму правдоподобия. Действительно, в соответствии с определением тСК без памяти ~ Р(гл~) Ы*,)=( — ' (-р)""' (7.33) где и — длина блоков у и х. Легко убедиться, что (7.33) является монотонно ш — 1 убывающей функцией р(у,х,.) при р<, что и доказывает эквивалентность т (7.31) и (7.32) для данного канала связи. В случае использования произвольного канала связи, например несимметричного или с памятью, декодирование по минимуму расстояния Хэмминга не обязательно будет оптимальной процедурой, однако ввиду простоты (7.32) этот алгоритм часто используется и в данных случаях. Если канал симметричен, но имеет память, то он может быть преобразован в ИСК без памяти, а следовательно, для него окажется оптимальным хэмминговскнй алгоритм декодирования после следующего преобразования канала связи, который называют иеремежеиием символов илн декорреляцией.
Как показано на рис. 7.2, кодовые блоки, содержащие п символов, номера которых отмечены верхними индексами 1, 2, ..., Ь, после их формирования предварительно заносятся в буферную память. После окончания формирования последнего 1.-го блока начинается передача символов этих блоков в канал 'связи "по столбцам" матрицы, находящейся в буферной памяти, т.е. последовательно передаются символы 1((), 1(21, „,, 1(~), 2(!),, 2(И, ..., и('1, ..., и(»1.
На приеме эти символы запоминаются в виде последовательных строк матрицы. После заполнения всех таких строк начинается декодирование по столбцам последовательных кодовых блоков с номерами (1), (2), ..., (2,). Видно, что каждая пара смежных символов в любом из кодовых блоков передается в канале связи с разнесением во времени Т.Т», где Т» — длительность канального символа. Если параметр 2, выбран достаточно большим, а зависимость между ошибками (память канала) убывает при разнесении передаваемых символов, то после такой процедуры можно практически полностью устранить память в канале связи. 1" 2'"' и ~и ио Рис.7.2.
Процедура перемежеиия символов 269 Определение б. Минимальным кодовым расстоянием д для заданного кода ~' будем называть минимальное расстояние по Хэммингу между всеми парами его несовпадающих кодовых комбинаций, т.е. с(= пйвр(х„х,). (7.34) ИзбЫточный код !г может использоваться в канале связи с помехами не только для декодирования (распознавания) действительно передававшихся сообщений, т.е.
фактически для исправления ошибок, но и для обнаружения ошибок. Естественным алгоритмом декодирования с обнаружением ошибок является принятие решения об отсутствии ошибок, когда принятая комбинация у совпадает с одной из разрешенных кодовых комбинациях, т.е. у=х, н Г, и обнаружение ошибок, если ухх, для всех х, и ~'. Очевидно, что в этом случае возможны ошибки декодирования, а именно принятие решения об отсутствии ошибки, в то время как они в действительности имеют место. Будем называть это событие необнаруженной ошибкой, а его вероятность — вероятностью необнаруженной ошибки, обозначая ее через р„о или рне(Р) для заданного кода К При рассмотренном выше алгоритме обнаружения ошибок необнаруженная ошибка может появиться тогда, и только тогда, когда передаваемая по каналу связи кодовая комбинация под воздействием помех перейдет на выходе в какую-либо другую кодовую (разрешенную) комбинацию.
Поэтому при равновероятном выборе кодовых комбинаций М р (~') = — ~~~ Р(у еГ, у ~! х, )х,). (7.35) 3=1 Определение 7. Будем говорить, что код г гарантированно обнаруживает или исправляет ошибки кратности не больше г при использовании некоторого алгоритма обнаружения или исправления ошибок, если кодовые слова после применения этих алгоритмов не будут содержать необнаруженных или неисправленных ошибок, когда кратность ошибки в канале связи не превосходит г. (Данный код может исправлять или обнаруживать ошибки и большей кратности, но это может иметь место не для всех образцов ошибок). Возможности кода обнаруживать ошибки определяются следующей теоремой. Теорема 7.3.
Если код имеет минимальное расстояние д, то он гарантированно обнаруживает ошибки кратности не более чем г, = д-1 Доказал!ельсл!во. Как было отмечено ранее, ошибка оказывается необнаруженной тогда, и только тогда, когда под воздействием помех в канале связи передававшаяся кодовая комбинация переходит в какую-либо другую кодовую комбинацию.
Но для зтого необходимо, чтобы образец ошибок имел кратность не меньше д, поскольку все кодовые комбинации по определению понятия минимального кодового расстояния отличаются друг от друга не меньше, чем в Ы позициях. Определение 8, Будем называть функцией кратности ошибки Р(п,м) в данном канале связи вероятность появления у ошибок на кодовом блоке длины п, В яастном случае тСК без памяти , ~ч рь,,)-с" ( ~,~ (!-р)" (7.36) Теорема 7.3 позволяет получить верхнюю границу для вероятности необнаруженной ошибки кодом Р'с минимаяьным расстоянием а': 270 Доказательство.
Пусть передавалось кодовое слово х~ и принято слово у, причем по уело~а-П вию теоремы р(у,х) < ~ — ~. Предположим, что сушествует кодовое слово хя которое нахо~г3' дится от принятого слова у на расстоянии Хэмминга не большим, чем слово хь и, следовательно, может произойти ошибочное декодирование этого слова вместо слова хь Этот факт ~ г-11 означает, что р(у,хз) я ~ — ~.
Применяя неравенство треугольника (7.30) к словам х„х., у, получаем (7.39) С другой стороны, выполнение (7.39) невозможно, поскольку по определению Ы для данного кода р(хьхф в. Следовательно, действительно передававшееся кодовое слово х, будет декодировано верно, и теорема доказана. Теорема 7.4 позволяет построить верхнюю границу вероятности ошибочного декодирования при использовании алгоритма Хэмминга в произвольном канале связи: р,„< ',> Р(п,~).
(7.40) -М" В частном случае тСК без памяти получаем из (7.36) и (7.40) р.,~ г с:( — ',)(1-р)''. =Н" Определение 9. Будем называть алгоритмом совместного исправления ошибок кратности до г„и обнаружения ошибок при использовании кода 1'с минимальным расстоянием И > 2г„+1 алгоритм, который по принятому слову у декодиРУет кодовое слово хь если Р(У,х,) <г„, и обнаРУживает наличие ошибки, если р(у,х,) > г„для всех кодовых слов хь 1 = 1, 2, ..., М. Свойства кода с заданными параметрами Ы и г„по совместному исправлению и обнаружению ошибок определяются следующей теоремой.
(7.41) 271 р (Г) < ХР(п,ч). (7.37) (Неравенство в (7.37) возникает потому, что код с минимальным расстоянием И может, вообше говоря, обнаруживать ошибки и кратности большей, чем И вЂ” 1.) Подставляя (7.36) в (7.37), получаем, что для тСК (в частном случае 2СК) без памяти р Р')<;~.С."~ — ",~ 11-р)"'. (7.38) т— Возможности кода по исправлению ошибок определяются следующей теоремой. Теорема 7.4. Если код имеет минимальное расстояние Ы, то при декодировании по минимуму расстояния Хэмминга он гарантированно исправляет ошибки кратноГс~-11 сти гн не более, чем ~ — ~, где 1х) означает целую часть х. (7.43) В качестве признака отсутствия стирания символа на 1-м тактовом интервале при оптимальном когерентном приеме противоположных сигналов (з(г),— з(г)1 на фоне белого шума можно использовать превышение некоторого порога абсолютным значением корреляцион- 1Т ного интеграла ~®ф)й, где т(г) — принимаемый непрерывный сигнал, а Т вЂ” длительность Р-Вт элемента сигнала (тактовый интервал, см.
гл. 5). Определение 10. Будем называть алгоритмом исправления стираний и ошибок такой метод декодирования, который измеряет расстояние Хэмминга между принятым блоком у и всеми кодовыми словами в нестертых позициях и декодирует то кодовое слово, для которого это расстояние минимально. Исправляющая способность алгоритма совместного исправления стираний и ошибок определяется теоремой. Теорема 7.6. Если код имеет минимальное расстояние д, то он может одновременно исправить г стираний и гя ошибок при выполнении следующего условия: а>2г„+г, +1. (7.44) Доказательство производится совершенно аналогично доказательству теоремы 7.4 с учетом того очевидного факта, что код' г; с длиной блоков п — г, образованный из комбинаций исходного кода ~' при вьгчеркивании в стертых позиций, имеет минимальное расстояние не менее, чем д — г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
