Главная » Просмотр файлов » Алгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v2.0

Алгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v2.0 (1127212), страница 2

Файл №1127212 Алгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v2.0 (Алгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v2.0) 2 страницаАлгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v2.0 (1127212) страница 22019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Сложность построения такой таблицы равна Õ(2n )6 , т.к. для каждого из 2m синдромов необходимоперебирать 2k решений очередной СЛАУ. В результате процедура декодирования произвольного линейного кодатребует экспоненциальных затрат как по памяти, так и по сложности алгоритма декодирования.Пример 2. Рассмотрим линейный код из примера 1. Пусть исходный вектор u = [0 1 1]T . Систематическоекодирование для него было получено раньше: v = [1 1 0 0 1 0]T . Пусть при передаче происходит ошибка вовтором бите, т.е. принятый вектор w = [1 0 0 0 1 0]T . Для декодирования w найдём его синдром 1 0  11 1 1 0 0 0 0 = 0 .s = Hw = 1 0 0 1 1 0 001 0 1 0 1 1 10Далее необходимо найти все решения системы He = s. Частное решение этой системы легко найти с учётомтого, что в столбцах 2, 4, 6 проверочной матрицы H стоит единичная подматрица.

Пусть ê1 = ê3 = ê5 = 0. Тогдаê2 = s1 , ê4 = s2 , ê6 = s3 , т.е. ê = [0 1 0 0 0 0]T . Решение однородной системы уже было найдено раньше на этапевычисления кодового расстояния d:0 1 0 1 0 1 0 10 1 0 1 1 0 1 00 0 0 0 1 1 1 1.G[u1 , u2 , . . . , u8 ] = 0 1 1 0 1 0 0 10 0 1 1 1 1 0 00 1 1 0 0 1 1 0Таким образом, все 8 решений системы He = s могут быть записаны как0 1 0 1 0 1 0 11 0 1 0 0 1 0 10 0 0 0 1 1 1 10 1 1 0 1 0 0 1 .0 0 1 1 1 1 0 00 1 1 0 0 1 1 0Выбирая среди них решение с наименьшим весом, находим e = [0 1 0 0 0 0]T , т.е. v̂ = w + e = [1 1 0 0 1 0]T .Циклические кодыРанее в курсе были рассмотрены т.н.

циклические подпространства Fnp , рассматриваемого как линейное пространство размерности n с элементами векторов из Fp . Напомним, что подпространство I называется циклическим, если вместе с любым вектором v = {v0 , v1 , . . . , vn−1 } ∈ I оно содержит и его циклический сдвиг6 СимволомÕ(x) обозначена сложность с точностью до логарифмических факторов, т.е. O(x logγ x).{v1 , . . . , vn−1 , v0 }. При дополнительном требовании линейности циклического подпространства I можно показать, что I является главным идеалом в фактор-кольце Fp [x]/(xn − 1), порождённым некоторым делителем g(x)многочлена xn − 1.

Переведём этот алгебраический результат на язык кодов с учётом p = 2.Назовём линейный блоковый (n, k)-код циклическим, если в нём любой циклический сдвиг кодового словаявляется кодовым словом. Поставим в соответствие произвольному вектору v = {v0 , v1 , . . . , vn−2 , vn−1 } ∈ {0, 1}nполином вида v(x) = v0 + v1 x + · · · + vn−2 xn−2 + vn−1 xn−1 . Тогда рассмотренное выше свойство главного идеала для циклического кода можно переформулировать следующим образом: для (n, k)-линейного циклическогоблокового кода найдется полином g(x) степени m = n − k такой, что1.

Все кодовые слова v(x) могут быть представлены как g(x)q(x), где q(x) – некоторый полином степени невыше, чем k − 1;2. Полином g(x) является делителем полинома xn + 1.Такой полином g(x) называется порождающим полиномом циклического кода. Любой полином, являющийсяделителем xn + 1, является порождающим для некоторого циклического кода длины n.Кодирование.

С учётом того, что для циклического кода любой кодовый полином v(x) делится на порождающий полином g(x), процедура кодирования может быть организована как v(x) = g(x)u(x), где u(x) – входящийполином степени не выше k − 1. Такое кодирование будет несистематическим. Оно соответствует рассмотрениюпорождающей матрицы кода G = [g 0 |g 1 | . .

. |g k−1 ], где базисные вектора g i определяются полиномами g(x)xi ,i = 0, . . . , k − 1.Для организации систематического кодирования полинома u(x) рассмотрим полином xm u(x), где m – числопроверочных бит кода и степень g(x). Поделим xm u(x) на g(x) с остатком:xm u(x) = g(x)q(x) + r(x),где deg r(x) < m. Тогдаxm u(x) + r(x) = g(x)q(x) ∈ C.Заметим, что deg xm u(x) ≥ m.

Таким образом, в векторном представлении полином xm u(x) + r(x) имеет вкрайних правых позициях элементы u(x). В результате процесс систематического кодирования u(x) может бытьреализован какv(x) = xm u(x) + mod(xm u(x), g(x)).Такая схема кодирования соответствует выбору порождающей матрицы кода с базисными векторами g i , определяемыми полиномами xm+i + mod(xm+i , g(x)).По аналогии с понятием проверочной матрицы для циклического кода можно ввести понятие проверочногополинома. Полином h(x) степени k называется проверочным, если выполнено свойствоg(x)h(x) = xn + 1.Соответственно, проверочный полином может быть найден по порождающему g(x) простым делением многочлена xn + 1 на g(x). Пусть v(x) – произвольный кодовый полином, т.е. он представим в виде v(x) = g(x)q(x).Тогдаv(x)h(x) = q(x) g(x)h(x) = 0.| {z }0Пусть проверочный полином имеет вид h(x) =какh0 h1 h2 .

. . 0h0 h1 . . .H=. . . . . . . . . . . .0 ... ...0Pkhi xi . Тогда нетрудно построить проверочную матрицу кодаhk0 ...00hk−1 hk0...0 ∈ {0, 1}m×n ....... ....... . .h0h1 . . . hk−1 hki=0Такой выбор проверочной матрицы соответствует рассмотрению базисных векторов hj , определяемых полиномами h(x)xj , j = 0, . . . , m − 1.Декодирование.

Назовём синдромом принятого полинома w(x) полином s(x) = mod(w(x), g(x)) =mod(v(x) + e(x), g(x)) = mod(e(x), g(x))7 . Как и раньше для случая линейных кодов синдром является нулевым многочленом тогда и только тогда, когда w(x) является кодовым словом. Общий алгоритм декодирования7 Очевидно,что синдром можно определить и с помощью проверочного полинома как s(x) = mod(w(x)h(x), xn + 1).циклического кода принципиально не отличается от общего алгоритма декодирования линейного кода.

В нёмрассматривается общее решение системы e(x) = s(x) + g(x)u(x) для всех возможных полиномов u(x) степениk − 1, а искомый полином ошибок определяется как решение с минимальным числом ненулевых слагаемых.Таким образом, для задания циклического кода достаточно определить порождающий или проверочныйполином. По сравнению с линейными кодами в циклических кодах операции умножения матриц на вектора ирешение СЛАУ заменяются на более простые операции умножения полиномов и деление полиномов с остатком.Однако, общий алгоритм декодирования по-прежнему имеет экспоненциальную сложность по k.Пример 3.

Пусть длина циклического кода n = 7. Для построения циклического кода необходимо сначаланайти разложение полинома x7 + 1 на неприводимые множители. Так как 7 = 23 − 1, то все ненулевые элементыполя F32 являются корнями x7 +1. Известно, что каждый многочлен над F2 содержит в расширении поля F32 вме23сте с любым своим корнем β также смежные корни вида β 2 , β 2 , β 2 , . . . . Пусть α – произвольный примитивныйэлемент поля F32 .

Тогда с учетом α7 = 1 легко найти разбиение всех элементов поля на смежные классы:(α, α2 , α4 ); (α3 , α6 , α5 ); α7 .Таким образом, многочлен x7 + 1 имеет один неприводимый делитель степени 1, а также два неприводимыхделителя степени 3. В результате получаем разложениеx7 + 1 = (x + 1)(x3 + x + 1)(x3 + x2 + 1).В качестве g(x) может выступать произвольный делитель x7 + 1.

Выберем в качестве g(x) многочлен x3 + x + 1.В результате получаем циклический (7, 4)-код.Пусть входной полином u(x) равен x3 + x2 . Его несистематическое кодирование находим какv(x) = u(x)g(x) = (x3 + x2 )(x3 + x + 1) = x6 + x5 + x4 + x2 .В бинарном представлении это соответствуетu = [0011], v = [0010111].Для осуществления систематического кодирования необходимо найти остаток от деления многочлена x3 u(x)на g(x).

В результате находимv(x) = x3 u(x) + mod(x3 u(x), g(x)) = x6 + x5 + mod(x6 + x5 , x3 + x + 1) = x6 + x5 + x.В бинарном представлении этот соответствуетu = [0011], v = [0100011].Таким образом, действительно биты входного сообщения u воспроизводятся в крайних правых битах кодовогослова v.Коды БЧХПолином mα (x) ∈ F2 [x] называется минимальным полиномом для элемента α ∈ Fl2 , если он является полиномомминимальной степени, для которого α является корнем.

В частности, минимальный полином для примитивногоэлемента α называется примитивным полиномом. Можно показать, что корнями минимального полинома mα (x)qявляются {α, α2 , α4 , . . . , α2 }. Данный набор элементов из поля Fl2 называется классом смежности для элементаα. Смежные классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можнопоказать, что полиномqYi(x + α2 ) = xq + λq−1 xq−1 + · · · + λ1 x + λ0i=1имеет коэффициенты из F2 и является минимальным полиномом для α, а также для всех элементов поля,входящих вместе с α в один смежный класс. Отсюда выводится метод построения минимального полинома длязаданного элемента поля α:1. Построить смежный класс, порождённый элементом α;i2.

Найти коэффициенты полинома mα (x) путем перемножения многочленов x + α2 для всех i = 1, . . . , q.В примере 3 для циклического кода был рассмотрен случай, когда длина кода n представима в виде 2l − 1. Вэтом случае корнями многочлена xn + 1 являются все ненулевые элементы поля Fl2 , а порождающими многочленами циклического кода могут быть только минимальные многочлены для некоторой совокупности элементовFl2 . Коды БЧХ являются подмножеством циклических кодов, которые существенно используют указанную связьмежду порождающим полиномом и элементами из Fl2 .

Прямым следствием такого подхода является то, что длины кодов БЧХ перестают быть произвольными8 .Итак, пусть n = 2l − 1, d = 2t + 1 ≤ n. Тогда кодом БЧХ называется (n, k, d)-линейный циклический код, вкотором порождающий многочлен g(x) определяется как минимальный многочлен для элементов α, α2 , . . . , αd−1из поля Fl2 , где α – произвольный примитивный элемент поля Fl2 , т.е.g(x) = НОК(mα (x), mα2 (x), . . . , mαd−1 (x)).Набор элементов α, α2 , . .

. , αd−1 называется нулями БЧХ-кода. Можно показать, что минимальное кодовое расстояние кода БЧХ не меньше, чем величина d. В результате БЧХ-коды по построению способны исправлять неменее t ошибок, где t = [(d − 1)/2].С учетом того, что все кодовые слова циклического кода делятся на g(x), а g(x) является минимальнымполиномом для выбранных нулей кода, тоv(x) ∈ C ⇔ v(αi ) = 0 ∀i = 1, . . . , 2t.Назовём синдромами принятого сообщения w(x) значения w(x) в нулях кода: si = w(αi ), i = 1, . . . , 2t. Всесиндромы равны нулю тогда и только тогда, когда w(x) является кодовым словом.Пример 4.

Рассмотрим БЧХ-коды для случая поля F32 = F2 [x]/(x3 + x + 1). Здесь l = 3, n = 7. Полином3x + x + 1 является примитивным полиномом над F2 . Обозначим через α ∈ F32 его произвольный корень.Построим код БЧХ, исправляющий не менее, чем t = 1 ошибку. Его порождающий полином g(x) строится какминимальный многочлен для элементов α, α2 . Эти элементы входят в один смежный класс (α, α2 , α4 ). Поэтомуg(x) = mα (x) = mα2 (x) = x3 + x + 1. В результате получаем (7, 4, 3)-код, являющийся кодом Хэмминга.Построим код БЧХ, исправляющий не менее, чем t = 2 ошибок. Его порождающий полином g(x) строитсякак минимальный многочлен для элементов α, α2 , α3 , α4 .

Характеристики

Тип файла
PDF-файл
Размер
372,29 Kb
Тип материала
Высшее учебное заведение

Список файлов учебной работы

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6521
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее