Ипатов В. Широкополосные системы и кодовое разделение сигналов (2007) (1151883), страница 73
Текст из файла (страница 73)
Введем несколько дополнительных определений. Расстоянием Хзжльинеа ап(г', ц) между двумя векторами 1'=(Уо,Л,...,У 1) и К= Ьо,О1,...,П 1) одной и той же длины и называется число позиций, на которых зти векторы имеют несовпадающие элементы () у'= д;. Весом Хзльмннга шп(1) вектора 1' называется число его ненулевых компонент. Если, например, Г = (01011), К = (11000), то йц(7, к) = 3, шп(т) = 3 и шн(к) = 2.
Нетрудно видеть, что г1п(г,к) = шн(т — к) и шн(%) = г1н(т,О), где 0 — нулевой вектор. Пусть передается кодовое слово и. ДСК превратит его в отличное фиксированное кодовое слово и (вызвав, тем самым, необнаруживаемую ошибку и выдачу декодером неверных битов данных, отвечающих н), если ошибки в символах произойдут на всех дп (п,ч) позициях, где и и ъ" различаются, и не произойдут на остальных и — дп(п, и) позициях (где символы слов совпадают). Тогда для ДСК без памяти, т. е. канала, в котором ошибки в последовательных символах независимы, вероятность Р(у = ч~п) вышеупомянутого превращения Р(у = у~п) рвн(нлб(1 р)™н(аоб Поскольку р ( 1/2 (в противном случае следовало бы просто переобозначить на выходе нуль единицей и наоборот), для снижения вероятности перепутывания кодовых слов и и н расстояние Хзмминга между ними должно быть как можно больше.
Рассмотрим теперь расстояния Хэмминга Ин(п,н) между всеми парами различных кодовых векторов кода У. Обозначим наименьшее среди них как дн и назовем его (минимальным) 9.2.Б Й, б~у ~ б ЗД9 кодовым расстоянием кода У: (9.2) с~в = ппп дн(п,и). афч ч,чав Любое кодовое слово может выступать в роли переданного, и, чтобы минимизировать риск перепутывания двух ближайших кодовых векторов, расстояние между ними, т. е.
кодовое расстояние Йн, должно быть максимально возможным. В частности, справедливо следующее утверждение. Ъ'тверждение 9.1. Код У обнаруживает любые Фа или менее символьных ошибок (вплоть до 1а ошибок), если и только если его кодовое расстояние Ын > $а + 1. Действительно, рассмотрим код с с~в ( 1а и выберем пару его ближайших кодовых векторов и, ч. Если Ин символов и, отличных от символов ч, искажены, и превращается в ч, означая существование необнаруживаемой конфигурации из не более, чем ~а символьных ошибок. Обратно, если расстояние между любыми кодовыми векторами больше 1а, не существует комбинации 1а или менее символьных ошибок, которая могла бы трансформировать одно кодовое слово в какое-либо другое.
Подобным же образом доказывается и следующий факт (задача 9.4). о'тверждение 9.2. Код У способен исправлять ~, или менее ошибочных символов, если и только если взо кодовое расстояние дн > 21~+ 1. 9.2.2. Линейные коды и их полиномиальное представление Отождествим двоичные кодовые символы 10, Ц с элементами конечного поля СР(2) (см.
~ 6.6) и рассмотрим посимвольные линейные операции над кодовыми словами кода У, основанные на арифметике Сг'(2). Нетрудно понять, что существует лишь одна нетривиальная операция такого рода, а именно посимвольное сложение: и = (ив,иы...,и„~), и = = (оьвы...,о„-1) ~ и+ и = (ив+ ио,и1+ ом...,и„1+ о„1). Если, например, и = (100111), ч = (010110), то и+ ч = (110001). Посимвольное вычитание самостоятельной роли не играет, попросту повторяя сложение, поскольку элементы СГ(2) противоположны самим себе. Подобным же образом посимвольное умножение на скаляр из Сг'(2) (т.
е. на 0 или 1) любого кодового слова либо превращает его в нулевой вектор, либо не меняет вовсе. Двоичный код У называется линейным, если сумма любых его кодовых векторов оказывается вновь некоторым кодовым вектором, принадлежащим У. Своим наименованием такой код обязан тому, что он является ~~~ЗбО Глава У. Канальное кодирование в широкополосных системах векторным (линейным) пространством над полем с»Р(2) [31, 33, 91], хотя последнее понятие в нашем контексте по существу не используется. Любой линейный код У длины п содержит в качестве кодового нулевой вектор (т.е. с и нулевыми компонентами), поскольку сумма произвольного вектора, входящего в У, с самим собой дает в точности нулевой вектор: и + и = О.
Следующий факт проясняет одну из причин особого интереса к линейным кодам. о'тверждение 9.3. Кодовое расстолние линейноео кода У равно минимальному весу Хэмминеа на мнолсестве всех ненулевых кодовых слов: (9.3) 4н = пппшн(п). нес нро Чтобы зто доказать, достаточно подставить Ип(п,»с) = «оп(п — »с) в (9.2) и заметить, что разность и — к = и' —. вновь кодовое слово У.
Как показывает (9.3), при оценке кодового расстояния в линейном коде, содержащем М слов, нет надобности в проверке всех М(М вЂ” 1)/2 пар несовпадающих векторов. Достаточно «взвесить» М вЂ” 1 ненулевых кодовых векторов, т.е. выполнить в М/2 раз меньше тестов, что --- с учетом обычно большого значения М вЂ” оборачивается заметным выигрышем.
Для понимания кодовых конструкций, обнаруживающих ошибки, из беспроводных 26 и 36 спецификаций полезно обратиться к'полиномиальному описанию линейных кодов. Сопоставим кодовому слову и = (ие,и1,...,и„1) кодовый полинам и(х) формальной переменной х, упорядоченный как и(Х) = и„1Х" +ип ЗХ" +... +ив, где по соглашению хе = 1. Такое полиномиальное представление, повсеместно используемое в теории кодирования, является на деле лишь вариантом х-преобразования, лежащего в основе анализа дискретных линейных систем, дискретной обработки сигналов, цифровой фильтрации и т. д.
[2, 71 Взаимно-однозначное соответствие между множествами кодовых слов и кодовых полиномов означает, что сумма двух кодовых полиномов и(х), е(х) линейного кода У является вновь кодовым полиномом и — 1 и — 1 того же кода. Если, к примеру, и(х) = ~ и;х', е(х) = 2, 'е;х« — кодовые '=0 1=0 п-1 полиномы слов и, »с линейного кода У, то и(х) + е(х) = ~"„(и« + е«) х« кодо«=0 вый полипом слова п+»с Е У, где сложение коэффициентов подчиняется правилам поля, которому они принадлежат, в нашем случае СР(2). Полиномиальная арифметика, используемая в анализе и построении кодов, включает еще две операции: умножение и деление с остатком.
».». » д, б р~ ~ б 36!«« Правила этих операций универсальны независимо от поля, которому принадлежат полиномиальные коэффициенты, однако, имея дело только с двоичными кодами, воспользуемся терминологией, характерной для двоичной арифметики. Рассмотрим произвольный (не обязательно кодовый) двоичный (т.е. с коэффициентами из СГ(2)) полипом а(з). Максимальная степень переменной г в этом полиноме с ненулевым коэффициентом называется сп«енеиью а(я) с обозначением с)ед а(з). Пусть а(л), 6(л) — два двоичных полинома, причем с1ед а(з) = т, с1ед 6(г) = «».
Тогда их произведением а(л)6(л) является полинам степени т+и, полученный в результате распространения коммутативного (лса = ая') и дистрибутивного законов на операции с формальной переменной л и суммирования всех коэффициентов прн одинаковых степенях ьс а(л)6(я) = (а,„я~+а, сл~ ~+ +аз)(Ь„л" +Ь„сл" ~+ -.
+6о) = = а„,Ь„л»" + (а,„Ь„« + а»6„)л»" ~+ ° + (асЬо+ аоЬс)я+ аоЬо = а;6» ; Разумеется, полагается, что л л" = лп»+", все операции над а;, Ь, выполняются в СЕ(2), и сомножители а;, Ь, в последней внутренней сумме с превосходящими степень полинома индексами равны нулю. Например, для двоичных полиномов а(г) = л4+ гз + 1, 6(л) = г» + л+ 1 произведение а(н)6(з) = ле + лз + з2 + я + 1 Алгоритм деления делимого а(л) на делитель 6(л) с остатком записывается равенством а(г) = 9(л)6(з) + г(л), (9 4) в котором о(л) — частное, а г(я) — остаток от деления. Единственность о(г), г(я) гарантируется соотношениями деда(г) = с1едд(л) + с1едЬ(л) и «1едг(л) < с1едЬ(л). Алгоритм (9.4) подобен «школьному» правилу деления целых с остатком, в котором роль абсолютных значений чисел передана степеням полиномов. Одним из приемов выполнения этой операции является «длинное деление», т.е.
пошаговое вычисление остатка и деление его на делитель до тех пор, пока степень остатка не окажется меньше степени делителя. На первой итерации 6(г) умножается на я, в степени, уравнивающей степень произведения со степенью делимого а(я). Вычитание (эквивзлентное сложению в СР(2)) полученного произведения из а(л) дает первый остаток, выступающий на второй итерации в роли делимого, и т. д. Подкрепим это следующей иллюстрацией. Пример 9.1.
Разделим а(г) = »4+ «»+ 1, на 6(») = ~» + л+ 1 с помошью алгоритма длинного деления (Зб2 Глава д. Канальное кодирование в широкополосных системах 2+ 2 +2+1 2 +22+ 1 + 4+ 3+ 2 2+ + 2 +2+1 После двух итераций имеем д(2) = 22 + 1, г(2) = 2, так что деление с остатком завершается результатом 24 + 22 + 1 = (22 + 1)(22 + 2 + 1) + 2. Как и в случае целых чисел, мы говорим, что а(х) делится на 6(х) (или 6(2) делит а(х)), если остаток равен нулю, т.
е. а(2) = д(х)6(х). Рассмотрим теперь линейный код 12 длины и со всеми кодовыми полиномами, делящимися на фиксированный полипом д(2) степени г ) 1. Любой кодовый полином в таком коде представим как и(х) = 6(х)д(2), и так как имеется всего 2" ' различных множителей 6(2), для которых степень произведения не превышает п — 1, такой код может содержать не более чем 2" ' кодовых слов. В действительности всегда можно пойти обратным путем и построить код с этим максимальным числом слов, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
