Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Построение полиномов с заданными корнями

Одно из фундаментальных положений классической алгебры утверждает, что любой полином f(x) степени m с действительными или комплексными коэффициентами всегда имеет ровно m действительных или комплексных корней x1, x2, …, xm, что означает справедливость разложения (при единичном старшем коэффициенте)

Последнее указывает способ построения полинома с заданными корнями x1, x2, …, xm. Если нужен действительный полином f(x) (т.е. с действительными коэффициентами или над полем действительных чисел), имеющий, однако, комплексные корни, в число корней f(x) наряду с любым комплексным корнем должен быть включен и комплексно-сопряженный с ним. Иначе говоря, комплексные корни любого действительного полинома всегда образуют сопряженные пары. Как выяснится далее, весьма похожая ситуация характерна и для полиномов над конечными полями.

Расширим нашу трактовку полиномов g(z) над конечным полем, рассматривая их как функции переменной z. Последняя, тем самым, с этого момента – не только формальный индикатор позиции символа, но и «истинная переменная», допускающая подстановку конкретного значения. В частности, взяв некоторый двоичный полином g(z) (т.е. полином над GF(2)), можно подставить в нем вместо z элемент некоторого расширения. Если при подстановке элемента aÎGF(2m) в двоичный полином g(z), g(a)=0, говорят, что g(z) имеет корень a (лежащий) в расширении GF(2m).

Пример 5.7.7 Рассмотрим полином g(z)=z3+z2+1. Легко убедиться, что у него нет корней в GF(2): g(1)= g(0)=1. Вместе с тем, обратившись к таблице поля GF(8) в примере 5.7.5, можно видеть, что g(V3)=V9+V6+1=V2+V2+1+1=0, и значит, V3 является корнем g(z) в поле GF(8).

Следующий факт свидетельствует об упомянутой ранее параллели с обычной алгеброй.

Теорема 5.7.4 Если двоичный полиномg(z)имеет кореньaв расширенном полеGF(2m) , то и все сопряженные элементаa –также корниg(z).

Пример 5.7.8Возвращаясь к предыдущему примеру, нетрудно убедиться, что полином g(z)=z3+z2+1 наряду с V3 имеет в GF(8) корни (V3)2=V6 (g(V6)=V4+V5+1=V2+V+V2+V+1+1=0) и (V3)4=V5 (g(V5)=V+V3+1=V+V+1+1=0), которые являются элементами, сопряженными с V3. Понятно, что при степени три g(z) не может иметь других корней, помимо найденных.

Двоичный полином наименьшей степени, для которого элемент aÎGF(2m) является корнем, называется минимальным полиномомa. Введем длянего обозначение ga(z) и сформулируем следующее утверждение.

Теорема 5.7.5 Пустьl– длина сопряженного цикла элементаa. Тогда

Теорема 5.7.6 Пусть GF(q) - расширение GF(2), где q=2m. Тогда все ненулевые элементы GF(q) являются корнями биномаzq11= zq1+1.

Как следствие этой теоремы справедливо следующее равенство

где все q–1 ненулевых элементов GF(q) выражены как степени примитивного элемента V.

Двоичные коды БЧХ

Накопленные к данному моменту знания открывают путь к ознакомлению с одним из наиболее замечательных классов блоковых кодов. Конструкция БЧХ дает один из редких примеров построения кодов с предсказуемыми и варьируемыми в широком диапазоне корректирующими свойствами. Коды, описываемые ниже, являются примитивными, входящими как частный (хотя и наиболее важный) подкласс в общее семейство БЧХ-кодов. Они имеют длину n=2m–1 и строятся на основе расширенного поля GF(2m). Обобщение теории БЧХ-кодов на p-ичный (p>2) алфавит не вызывает затруднений, однако недвоичные БЧХ-коды, за исключением кодов Рида-Соломона не столь привлекательны с точки зрения приложений. Принцип построения БЧХ-кодов декларируется следующим утверждением

Теорема 5.8.1 (теорема БЧХ). Пусть полином g(z) имеет в расширенном поле GF(2m) корни V, V2, …, Vs , где V – примитивный элемент поля GF(2m).Тогда циклический код с порождающим полиномом g(z) имеет минимальное расстояние d, не меньшее s+1.

Для доказательства теоремы предположим, что имеется кодовое слово веса s или менее. Делимость его кодового полинома u(z) на порождающий g(z) означает обращение этого полинома в нуль при z=Vi, i=1,2, …, s:

где j1, j2, …, js обозначают позиции компонентов слова, которые могут быть ненулевыми. Как видно, существование кодового слова веса s или менее равносильно существованию ненулевого решения квадратной s´s системы линейных уравнений с нулевой правой частью. Подобное решение существует только при вырожденной матрице системы. Матрица же нашей системы (ассоциированная с известной матрицей Вандермонда) имеет специфический вид

и не может быть вырожденной, если все элементы первой строки различны. Но последнее имеет место всегда, так как ς - примитивныйэлемент и 2m–1> >j1>j2>…>js³0.

Теперь алгоритм построения БЧХ-кодов можно описать следующим образом. Для значения m, обеспечивающего необходимую длину кода n=2m–1, выбирается примитивный полином f(x) и строится расширенное поле GF(2m), как это сделано в примере 5.7.6. После этого в поле GF(2m) выбираются степени примитивного элемента
V, V2, …, Vs, которым предстоитслужить корнями порождающего полинома. Любой из них, однако, должен войти в число корней порождающего полинома только вместе со всеми своими сопряженными. Таким образом, вместе с элементом V придется взять и элементы V2, V4, … , придя тем самым к сомножителю порождающего полинома g(z) согласно теореме 5.7.5:

где l1 – длина сопряженного цикла элемента V, равная m вследствие примитивности V. Полином g1(z) – является двоичным полиномом минимальной степени, имеющим корень V, т.е. минимальным полиномом V. Следующим корнем порождающего полинома должен быть элемент V2, уже учтенный сомножителем g1(z), так как он сопряжен с V. Если s>2, следующим корнем порождающего полинома должен быть элемент V3 также со всеми своими сопряженными (V3)2, (V3)4, … , что означает включение в g(z) сомножителя в виде минимального полинома элемента V3

где l3 – длина сопряженного цикла для V3. Подобные шаги продолжаются пока не будут найдены минимальные полиномы для всех элементов множества V, V2, …, Vs,не охваченных ранее. По исчерпании всех необходимых корней порождающего полинома g(z) последний строится как произведение всех найденных минимальных полиномов:

Гарантией того, что построенный таким образом полином можно использовать как порождающий для циклического кода, служит делимость на него бинома zn1, где
n=2m1 (см. теорему 5.2.2). В самом деле, полином g(z) является произведением некоторых биномов вида z–a с различными ненулевыми элементами aÎGF(2m), тогда как в силу теоремы 5.7.6 бином zn1 есть произведение всех подобных биномов.

Пример 5.8.1 Построим порождающий полином g(z) БЧХ-кода длины n=231=7, исправляющего любую однократную ошибку. Необходимое для этого расширенное поле GF(8) уже построено в примере 5.7.6. Поскольку s=2t=2, корнями порождающего полинома должны быть элементы V и V2. Минимальный полином элемента V имеет вид g1(z)=(z+V)(z+V2)(z+V4)= =z3+(V+V2+V4)z2+(VV2+VV4+V2V4)z+VV2V4. Но V+V2+V4=V+V2+V+V2=0, VV2+VV4+V2V4= =V3+V5+V6=V+1+V2+V+1+V2+1=1, VV2V4=V7=1, так что g1(z)= z3+z+1. Элемент V2, уже учтен в g1(z), а других обязательных корней g(z) нет, поэтому g(z)= =g1(z)=z3+z+1. Поскольку deg(g(z))=3, число информационных символов кода k=4, и, таким образом, построенный код оказался циклической версией (7,4) кода Хэмминга, исправляющего любую однократную ошибку.

Если изменить условия примера, потребовав исправления до двух ошибок (t=2Þs=4), множество обязательных корней полинома g(z) пришлось бы расширить до V, V2, V3, V4. Поскольку элементы V, V2 and V4 входят в один и тот же сопряженный цикл, т.е. уже охвачены минимальным полиномом g1(z), остается найти лишь минимальный полином для V3 (корнями которого будут и сопряженные с ним элементы V6 и V12= V5). Степень последнего равна трем, так что степень g(z) окажется равной шести, и полученный код есть тривиальный (7,1) код с повторением, передающий лишь один бит информации.

Разумеется, в наши дни системный дизайнер свободен от необходимости поиска порождающих полиномов БЧХ-кодов, поскольку подобная работа давно проведена, и детальные таблицы готовых к употреблению полиномов можно найти во многих источниках. Однако любой инженер или аналитик, причастный к канальному кодированию, должен уметь быстро оценивать параметры БЧХ-кодов. Грубую нижнюю границу числа информационных символов БЧХ-кода легко вывести, учтя, что любая четная степень V2i примитивного элемента V входит в сопряженный цикл элемента меньшей степени Vi и, следовательно, охвачена некоторым уже построенным минимальным полиномом. Как результат, общее количество сопряженных циклов для всех обязательных корней порождающего полинома не больше s/2=t (при s=2t), а так как длина любого цикла не превосходит m, параметры БЧХ-кода подчиняются соотношениям

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

Пример 5.8.2 Сколько информационных бит содержит БЧХ-код, исправляющий любую однократную ошибку? Для ответа на этот вопрос заметим, что, поскольку t=1, обязательными корнями порождающего полинома g(z) являются V и V2. Так как они принадлежат одному сопряженному циклу V, V2, … , длины m, g(z)=g1(z), причем deg(g(z))=m. Поэтому k=n–deg(g(z))=2m–m–1, т.е. БЧХ-код, исправляющий однократные ошибки, есть попросту циклическая версия кода Хэмминга.

Пример 5.8.3 Найдем точное число информационных бит БЧХ-кода длины n=31, исправляющего до 5 ошибок. Корнями его порождающего полинома должны быть элементы V, V2, V3, V4, V5, V6, V7, V8, V9, V10. Сопряженный цикл элемента V: V, V2, V4, V8, V16 (V32=V) охватывает, как видно, четыре обязательных корня V, V2, V4, V8 . Сопряженный цикл V3: V3, V6, V12, V24, V48=V17 (V34= V3) поглощает корни V3, V6 , доводя общее число корней до 6. Сопряженный цикл V5: V5, V10, V20, V40= V9, V18 (V36=V5) добавляет еще три корня V5, V9, V10. Последний необходимый корень порождающего полинома V7 имеет сопряженный цикл V7, V14, V28, V56=V25, V50=V19 (V38=V7). В итоге порождающий полином является произведением четырех минимальных полиномов, степень каждого из которых равна пяти, откуда deg(g(z))=4·5=20, и k=n–deg(g(z))=11. Примечательно, что истинное число информационных символов значительно превысило значение, предсказанное нижней границей: k³315·5=6.

Коды Рида-Соломона

Если при построении порождающего полинома g(z) согласно теореме БЧХ игнорировать сопряженные циклы элементов V, V2, …, Vs и формировать g(z) как произведение только самих биномов z–Vi, i=1, 2, …, s, порождающий полином окажется недвоичным. Вслед за ним недвоичным окажется и сам код: его символы будут принадлежать q-ичному алфавиту, где q=2m, т.е. расширенному полю GF(2m). В то же время сопряженные циклы были нужны только для того, чтобы «втиснуть» g(z) в множество двоичных полиномов, с точки же зрения достижения желаемого расстояния надобности в них нет. Иначе говоря, q-ичный код (q=2m) с порождающим полиномом

называемый кодом Рида-Соломона (кодом РС)полностью удовлетворяет условиям теоремы БЧХ, и, значит, имеет минимальное расстояние d³s+1. Длина такого кода n=q–1=2m–1 символов (q- ичных, не двоичных!) и так как степень g(z) теперь равна в точности s, число информационных символов (не битов, q-ичных символов!) k=n–s. Отсюда следует, что d³n–k+1. В то же время согласно границе Синглтона для любого кода d£n–k+1. Поэтому расстояние d и разность n–k+1 в точности равны, и параметры кодов РС

где свобода выбора числа информационных символов k ограничена лишь одним: с увеличением k на единицу кодовое расстояние уменьшается также на единицу.

Так как коды РС лежат на границе Синглтона, они оптимальны по критерию расстояния среди всех 2m-ичных кодов той же длины и скорости.

Разумеется, любой 2m-ичный символ можно записать как двоичный m-битовый блок. Подобное “раскрытие” символов кода РС даст двоичный код длины nb=mn=m(2m1) с числом информационных битов kb=mk и скоростью R=kb/nb=k/n. При этом, однако, нет оснований рассчитывать на увеличение кодового расстояния, так что для полученного кода вновь d=n–k+1=(nb–kb)/m+1, и в классе двоичных он не обладает выдающимися свойствами в части исправления случайных ошибок. С другой стороны, такой код весьма эффективен в борьбе с так называемыми пакетами ошибок: пакет, накрывающий до
t=(d–1)/2 последовательных 2m-ичных символов искажает примерно в m раз больше последовательных двоичных символов. Но ведь любая такая конфигурация ошибок корректируется в силу исправления кодом РС вплоть до t ошибок! Поэтому “двоично-представленный” код РС исправит любой пакет “двоичных” ошибок вплоть до длины, близкой к mt.

Пример 5.9.1 Найдем порождающий полином восьмеричного кода РС, исправляющего ошибки вплоть до двукратных. Так как этот код должен иметь расстояние d=5, то s=4 и корни его порождающего полинома ς, ς2, ς3, ς4.

В итоге

где использована таблица из Примера 8.2.5. Восьмеричный кодовый вектор, соответствующий этому кодовому полиному u=(ς3, ς, 1, ς3, 1, 0, 0), имеет вес 5. Обращаясь вновь к Примеру 8.2.5 и представляя символы GF(8) трехразрядными двоичными числами, получим двоичный кодовый вектор u=(011010001011001000000).

В заключение заметим, что любой БЧХ-код можно, конечно, преобразовать в укороченный без потери корректирующей способности. Поэтому коды РС сохраняют при укорочении оптимальность по отношению к границе Синглтона. Еще одна ремарка касается выбора корней в конструкции БЧХ. Легко убедиться, что если в теореме БЧХ ряд s последовательных корней начинается с ςj, имея вид ςj, ςj+1, …, ςj+s–1 при произвольном j, утверждение теоремы остается справедливым. Иногда j=0 или иное предпочтительно по сравнению с j=1.

Тема 6 Сверточные коды

Введение в сверточные коды

Наряду с блоковыми кодами существует обширный и эффективный класс древовидных или решетчатых кодов, среди которых особо интересны сверточные коды. Отличительной их чертой (в сравнении с блоковыми) является специфический способ отображения потока информационных символов (битов) в кодовые слова. При блоковом кодировании непересекающиеся последовательные k-битовые блоки источника преобразуются в последовательные непересекающиеся n-символьные кодовые слова, каждое из которых защищает лишь «собственный» k-блок информационных битов и занимает в реальном времени интервал, отведенный для передачи именно этого блока (см. рисунок, соответствующий параметрам k=4, n=7, R=4/7).

Сверточное (вообще, решетчатое) кодирование предполагает несколько иное отображения информационных битов в кодовые символы. Поток битов источника как бы просматривается сквозь скользящее окно шириной в m битов и все m битов, попадающие в данный момент в окно, преобразуются в группу из n символов кода, передаваемую в течение длительности одного информационного бита. После этого окно сдвигается вправо на один бит и обновленный m-блок информационных битов отображается в следующую n-символьную кодовую группу и т.д. В итоге вместо последовательных изолированных во времени слов, характерных для блокового кода, получается непрерывный кодовый поток, в котором каждая группа из n символов отвечает за защиту текущего бита данных вместе с m–1 предшествующими.

Параметр m сверточного кода показывает, сколько битов источника влияют на текущую n-символьную кодовую группу, и называется длиной кодового ограничения. На рисунке выше m=4 и n=2.

Стандартная сема сверточного кодера базируется на регистре сдвига, содержащем m–1 двоичных ячеек (элементов задержки), единственная функция которых состоит в запоминании m–1 прошлых битов, которые вместе с текущим битом следует закодировать в текущую n-символьную кодовую группу. Сама операция кодирования выполняется n сумматорами по модулю 2. Ключ S осуществляет мультиплексирование (последовательное подключение всех сумматоров к общему выходу), с тем чтобы разместить на длительности одного бита данных всю текущую n-символьную кодовую группу. После кодирования текущего и m–1предыдущих битов содержимое регистра сдвигается вправо, на вход поступает новый бит, а «старейший» покидает регистр и на дальнейшие кодовые символы не влияет.

Если подать на вход этого устройства k информационных битов, на выходе появится последовательность длиной не kn, а (k+m–1)n символов, поскольку регистр сдвига обнулится только после m–1 дополнительных тактов. Поэтому истинная скорость сверточного кода R=k/(k+m–1)n. Традиционно, однако, используется значение скорости, соответствующее k>>1: R=1/n. Как видно, возможные скорости сверточных кодов рассмотренного типа ограничены значениями {1/2, 1/3, 1/4, ...}. В принципе изложенную идею сверточного кодирования нетрудно модифицировать так, чтобы сделать возможными любые скорости вида l/n с произвольными натуральными l и n, l<n. Для этого сдвиг скользящего окна должен производиться не на один, а на l битов, и группа n кодовых символов должна соответственно занимать интервал, отвечающий l информационным битам. В наши дни, однако, подобный способ кодирования со скоростями l/n практически не применяется, проигрывая в сложности альтернативному варианту, который будет рассмотрен позднее.

Как должно быть ясно, любой сверточный код полностью задается длиной кодового ограничения и схемой соединения сумматоров с ячейками памяти регистра сдвига. Названные соединения принято описывать порождающими полиномами gi(z), i=1, 2, …, n. Степень 0, 1,…, m–1 формальной переменной z в порождающих полиномах соответствует порядковому номеру ячейки регистра сдвига, а коэффициент gij при zj в gi(z) равен единице, если и только если i-я ячейка регистра имеет соединение с j-м сумматором по модулю два.

Пример 6.1.1 Рассмотрим сверточный кодер, показанный ниже.

Он содержит двухразрядный регистр сдвига и, следовательно, формирует код с длиной кодового ограничения m=3. Скорость этого кода R=1/2, так как на каждый информационный бит приходится два кодовых символа. Порождающие полиномы кода

 

Удобно восьмеричное представление порождающих полиномов: все коэффициенты полинома выписываются слева направо и читаются как одно двоичное число, преобразуемое затем в восьмеричное. В примере выше (g1(z), g2(z))=(5, 7), тогда как, к примеру, полиному g(z)=1+z+z3+z6 отвечает восьмеричное представление 151. Прямо из определения порождающих полиномов следует, что наибольшая из их степеней всегда на единицу меньше длины кодового ограничения. Другими словами, память регистра сдвига (число его ячеек) совпадает с максимальной из степеней порождающих полиномов.

Если какой-либо из порождающих полиномов имеет нулевую степень (без потери общности можно считать, что это g1(z)): g1(z)=1, сверточный код называется систематическим, поскольку текущий информационный бит явно присутствует как первый символ в кодовой n-группе. Следует, однако, отметить, что при формировании сверточных кодов вышеописанным способом эквивалентности между систематическими и несистематическими кодами (в отличие от блоковых кодов) нет, причем несистематические, как правило, эффективнее.

Нетрудно убедиться в линейности сверточных кодов. Более того, само их название связано с тем, что сверточный кодер есть не что иное, как двоичный линейный КИХ-фильтр (трансверсальный фильтр), т.е. устройство, вычисляющее свертку входного вектора с вектором коэффициентов фильтра.

Вполне понятно, что отыскание хорошего сверточного кода сводится к подбору подходящих порождающих полиномов. Что касается памяти m–1, естественная общая тенденция состоит в том, что ее увеличение способствует повышению помехоустойчивости кода. Поиск же самих порождающих полиномов, в противоположность ситуации, характерной для циклических кодов, базируется в большей степени на компьютерном переборе, чем на серьезной теоретической поддержке.

Одно из оснований популярности сверточных кодов в современных телекоммуникациях – существование элегантного и ресурсосберегающего алгоритма декодирования (алгоритма Витерби).

Последнее изменение этой страницы: 2016-06-09

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...