Ипатов В. Широкополосные системы и кодовое разделение сигналов (2007) (1151883), страница 74
Текст из файла (страница 74)
е. передающий к = и — г информационных битов, отталкиваясь от заданного полинома д(х) фиксированной степени г. Для этого достаточно использовать к = и — г битов данных Ьш Ьы, ..,Ьь 2 в качестве коэффициентов полинома данных 6(х) = Ьь 12~ ~ + Ьь 2х~ 2+ ° + Ьз и сконструировать соответствующий кодовый полипом как произведение и(х) = Ь(х)д(х). При этом 2" различным й-битовым блокам данных взаимно-однозначно соответствуют столько же кодовых полиномов степени п — 1 или менее. Линейность такого кода легко проверяется (задача 9.11). В описанной конструкции полинам д(х) называется порождающим полинольол4 кода У.
Отметим, что число избыточных или проверочных символов подобного кода всегда равно степени порождающего полинома г. Когда полипом данных 6(х) напрямую умножается на порождающий полипом д(х), кодовое слово, отвечающее полиному и(х) = 6(х)д(х), оказывается несистематическим, т. е. биты данных в нем не видны явно на заранее оговоренных позициях. Для получения систельатического кода, в котором, например, последними к символами были бы непосредственно информационные биты, а г = и — й первыми — проверочные символы, можно определенным образом переупорядочить кодовые слова.
При этом исходное множество кодовых слов останется прежним, изменится лишь соответствие между блоками битов данных и кодовыми словами. Умножим полином данных 6(х) на 2' = х" ~, придя к полиному х" ~6(х) О.Л.Б д, б~~ ~ б 36ф степени не выше п — 1. Если остаток г(я) от деления этого произведения на д(я) отбрасывается (или прибавляется к з" "6(я) в двоичном случае), результат делится на порождающий полипом д(я), т. е. становится кодовым полиномом. Последний, имея вид и(я) = я" ~6(з) + г(з), отвечает систематическому кодовому слову, так как биты данных являются в точности 6 старшими коэффициентами з" ~6(я), и прибавление остатка г(з) степени меньшей, чем г = п — Й, на них повлиять не может. Пример 9.2. Найдем кодовое слово линейного (5„2) кода с порождающим полвномом д(я) = гз + юэ + 1, соответствующее информационным битам Ьэ = 1, 61 = 1. При этом Ь(я) = я + 1, я" ЯЬ(я) = э4 + ээ„и после деления на д(я) получается остаток г(я) = я.
Сложение г" ~6(г) с этим остатком дает кодовый полипом и(э) = ю~+г~+г = яд(г), соответствующий систематическому кодовому слову, посяедними двумя символами которого являются биты данных. Я.2.3. Вычисление синдрома и обнаружение ошибок Пусть кодовое слово и линейного кода У передается по ДСК. Элементы выходного двоичного наблюдения у, искаженные каналом, будут отличаться от переданных символов, что можно выразить равенством (9.5) у =п+е, где е — вектор ошибок, в котором нули и единицы стоят на позициях неискаженных и искаженных символов соответственно. Так, если слово и = (01011) из примера 9.2 трансформировано ДСК в наблюдение у = (11110), вектор ошибок е = (10101).
Подобно кодовым словам наблюдение у = (до,уы...,9„1) и вектор ошибок е = (ею ем..., е„1) можно представить в полиномизльной форме у(г) = 9„1з" ~+у„зя" ~+ +до и е(з) = е„1зв 1+ е„зз" ~ + . -. + ео. Тогда (9.5) примет вид д(я) = и(з) + е(з). Пусть д(я) — порождающий полипом кода У. Остаток л(з) от деления полинома наблюдения д(я) на д(г) называется синдромом. Поскольку любой кодовый полипом делится на д(я), синдром повторяет остаток от деления полинома ошибок е(г) на д(я). Следовательно, ненулевой синдром однозначно свидетельствует о наличии ошибок в наблюдении у, и обнаружение ошибок может быть реализовано как вычисление синдрома по наблюдению у и решение о наличии ошибок всякий раз, когда синдром не равен нулю.
Разумеется, обнаружению поддается не любая конфигурация ошибок, и любой необнаруживаемый вектор ошибок всегда является некоторым ~~~364 Глава д. Канальное кодирование в широкополосных системах кодовым вектором. Действительно, если е(х) — кодовый полипом, то он делится на д(х) и синдром равен нулю. Обратно, нулевой синдром означает, что е(г) делится на д(х), но любой полипом степени не выше и — 1, делящийся на д(г), есть кодовый полином. Пример 9.3.
Пусть переданное кодовое слово и = (01011) (5,2) линейного кода трансформировано ДСК в у = (11001), т. е. произошла двукратная ошибка. Деление у(х) = г~ + х+ 1 па д(х) = ха + г~ + 1 дает ненулевой синдром в(х) = с~, сигнализируя о наличии ошибок. В противоположность этому, если бы наблюдением был вектор у = (11101), соответствующий трехкратной ошибке, синдром оказался бы равным нулю: у(х) = х4 + сэ + х+ 1 = (х+ 1)д(х), и ошибки не были бы обнаружены. Нередко обнаруживающую способность линейного кода характеризуют долей необнаруживаемых конфигураций ошибок среди всех возможных. Так как общее число различных векторов ошибок равно 2", из которых только 2~ повторяют кодовые слова и не могут быть обнаружены, указанная доля составляет 2 (и ") = 2 ".
Рассмотренные вьппе линейные коды, построенные на основе порождающих полиномов, известны как циклические или укороченные циклические. Когда их назначение исчерпывается лишь обнаружением (но не исправлением) ошибок, они нередко упоминаются под названием ииклических избьппочных кодов (сус(ьс гсйипйапсу сосок /сойсв/ — СВС)1. 9.2.4. Выбор порождающих полиномов для СН,С Экспоненциальное снижение доли необнаруживаемых ошибок с ростом числа проверочных символов может мотивировать использование порождающих полиномов высоких степеней. Не следует забывать, однако, что проверочные символы представляют собой в определенном смысле непроизводительные затраты, и чрезмерное их число означает нерациональное расходование частотного ресурса.
Как правило, СВС используются на высших уровнях системных протоколов для проверки качества кадров данных, восстановленных на физическом уровне, т.е. после утилизации потенциала значительно более мощных кодов с исправлением ошибок. По этой причине символьные ошибки, нейтрализация которых является задачей СНС, достаточно редки, и вероятность многих ошибок в пределах кодового слова с сотнями символов обычно весьма мала.
В этом свете обнаружение трехкратных ошибок на кодовое слово нередко считается вполне приемлемым. Опишем процедуру синтеза СНС, удовлетворяющего этому условию. 'Ниже используется англоязычная аббревиатура СНС, принятая пе только в зарубежных, по и во многих отечественных источниках. Возьмем двоичный примитивный полипом д1(х) степени т (см. 3 6.6). Важный факт, доказываемый в алгебре расширенных полей, состоит в том, что примитивный полином степени т не может делить бином х'+ 1 ненулевой степени 1 < 2 — 1 (30, 32]. Из этого можно сделать следующий вывод. 'Утверждение 9.4.
Код У с порождающим полиноыом д(х) = (я+1)д1 (х) степени т обнаруживает вплоть до трех ошибок, если еео длина и < < 2 — 1. Вследствие линейности кода 11 (см. (9.3)) и утверждения 9.1 нужно лишь доказать, что минимальный вес ненулевого слова У не меньше четырех.
Любой кодовый полипом и(х), делящийся на х + 1, может быть представлен в виде и(х) = д(х)(г + 1). Хотя х — — формальная переменная, последнее равенство останется верным при подстановке х =- 1 в обе его части: и(1) = и„1+ ип з + + ио = О, что говорит о четности числа ненулевых элементов слова, т.е. четности его веса.
Слово веса два с ненулевыми г-м и д-м символами (д > г) не может принадлежать коду о', так как его кодовый полипом и(х) = ьд + г' = х'(1+ ху ') не делился бы на д1(х), поскольку последний, будучи неприводимым, не содержит множителя х и не делит 1+ ьд ' (д — 1 < и < 2т — 1) как примитивный. Таким образом, наименьший возможный вес ненулевого слова ь1 равен четырем. Теперь ясно, как выбрать подходящий порождающий полипом СНС.
При желаемой длине кода и следует лишь найти примитивный полипом д1(х) степени т > (1обз(п + 1)1 и взять в качестве порожда1ощего полином д( ) =( +1)д1( ). Коды СВ.С подобного типа оказываются не чем иным, как популярными кодами Хэмминга (при и < 2т — 1 — укороченными) с исключенными словами нечетного веса. В альтернативном применении они позволяют исправлять любые однократные и обнаруживать любые двукратные ошибки. Пример 9.4.
Ряд СНС кодов фигурирует в спецификациях 2С и ЗС систем [18, 69, 92]. Например, во всех трех стандартах (сйпаОпе, %СРМА и сйпа2000) используется код с порождающим полиномом д(х) = х1в + хм + хь+ 1 = (х+ 1)д1(х), где д1(х) = х +х + х' + х +х + х + х + э+ 1 — примитивный полипом. Подобным же образом порождающие полиномы других СНС кодов этих стандартов (степеней 30, 24 я т. и.) факториэуются в произведения бинома х + 1 и примитивного полинома. 9.3. Сверточные коды Сверточные коды широко применяются в современных телекоммуникациях как эффективный инструмент надежной передачи данных по каналам ~~( 366 Глава Р. Канальное кодирование в танронополосных системах с шумами.
Среди древовидных (решетчатых) кодов, к которым они принадлежат как подкласс, сверточные коды отличаются линейностью алгоритмов кодирования. Разница между сверточными и блоковыми кодами в определенной мере размыта: любой сверточный код можно трактовать как блоковый адекватно большой длины. Специфику и причины особой популярности сверточных кодов можно скорее связать с их рекуррентной природой, открывающей путь к построению особо экономичной в отношении вычислительного ресурса процедуры декодирования с исправлением ошибок — алгоритма Витерби. 9.3.1. Сверточный кодер Общую идею сверточного кодирования можно обьяснить следующим образом.
Возьмем блок (вектор) р, последовательных битов источника и линейно преобразуем его в и > 1 выходных двоичных кодовых символов, занимающих временной интервал, равный длительности одного бита источника. Линейность по отношению к векторам с компонентами из поля Сг (2) означает суммирование по модулю два некоторых выбранных компонент. После этого обновим блок битов источника, введя в него один новый бит, с одновременным исключением самого старого. Тем самым мы вновь имеем блок из м, битов источника, запаздывающий на один бит относительно предыдущего (и содержащий ь; — 1 прежних битов и один новый), который кодируется по тому же правилу в и новых кодовых символов. Подобные шаги непрерывно повторяются один за другим, с вовлечением каждый раз одного нового бита взамен старейшего.
Окно в ть битов Длительность бита ~+ - ' тнл и, Битовый поток л символов кода л символов кода л символов кода Рис. 9.2. Принцип сверточиого кодирования Рис. 9.2 иллюстрирует данную процедуру для случая ис = 3, и = 3: кодер как бы просматривает битовый поток источника сквозь скользящее окно ширины ис и кодирует все биты, видимые на текущем шаге, в п кодовых символов. После каждого шага окно смещается вправо на один бит я.я.ср . е ЗД7 источника н выполняется следующий шаг.
Число битов источника, влияющих на кодовые символы на одном шаге, называется длиной кодового ограничения. 1 ! оо* о1' г и 1 "о "о " "о Рис. 9.3. Сверточный кодер Описанный принцип можно технически воплотить в виде структуры, представленной на рнс. 9.3, где регистр сдвига, состоящий нз ос — 1 ячеек памяти, хранит ос — 1 предшествующих битов источника. Вместе с поступающим битом онн подаются на линейную логическую цепь, содержащую и сумматоров по модулю два.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
