Двоичные коды Боуза-Чоудхури-Хоквингема (БЧХ): Двоичный код БЧХ имеет параметры: п = 2х — 1, к = 2х — lu-t — 1, d =

Коды Боуза-Чоудхури-Хоквингема (стр. 1 из 2)

Двоичные коды Боуза-Чоудхури-Хоквингема (БЧХ):  Двоичный код БЧХ имеет параметры: п = 2х - 1, к = 2х - lu-t - 1, d =

РЕФЕРАТ

По курсу “Теория информации и кодирования”

на тему:

«КОДЫ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА»

БЧХ коды

Коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс циклических кодов, исправляющих кратные ошибки, т. е. две и более (d0 ³ 5).

Теоретически коды БЧХ могут исправлять произвольное количество ошибок, но при этом существенно увеличивается длительность кодовой комбинации, что приводит к уменьшению скорости передачи данных и усложнению приемо-передающей аппаратуры (схем кодеров и декодеров).

Методика построения кодов БЧХ отличается от обычных циклических, в основном, выбором определяющего полинома P(х). Коды БЧХ строятся по заданной длине кодового слова n и числа исправляемых ошибок S , при этом количество информационных разрядов k не известно пока не выбран определяющий полином.

Рассмотрим процедуру кодирования с использованием кода БЧХ на конкретных примерах.

Пример Построить 15-разрядный код БЧХ, исправляющий две ошибки в кодовой комбинации (т. е. n = 15, S = 2).

Решение:

1. Определим количество контрольных m и информационных разрядов k

m £ h S .

Определим параметр h из формулы

n = 2h-1, h = log2(n+1) = log216 = 4,

при этом: m £ h S = 4×2 = 8; k = n-m = 15-8 = 7.

Таким образом, получили (15, 7)-код.

2. Определим параметры образующего полинома:

— количество минимальных многочленов, входящих в образующий

L = S = 2;

— порядок старшего (все минимальные — нечетные) минимального многочлена r = 2S-1 = 3;

— степень образующего многочленаb = m £ 8.

3. Выбор образующего многочлена.

Из таблицы для минимальных многочленов для кодов БЧХ (см. приложение 4) из колонки 4 (т. к. l = h = 4) выбираем два минимальных многочлена 1 и 3 (т. к. r = 3):

M1(x) = 10011;

M2(x) = 11111.

При этом

P(x) =M1(x)×M2(x)=10011´11111=111010001= x8+ x7+ x6+ x4+1.

4. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 15. Остальные строки матрицы получаем в результате k-кратного циклического сдвига справа налево первой строки матрицы.

Строки образующей матрицы представляют собой 7 кодовых комбинаций кода БЧХ, а остальные могут быть получены путем суммирования по модулю 2 всевозможных сочетаний строк матрицы.

Процедура декодирования, обнаружения и исправления ошибок в принятой кодовой комбинации такая же, как и для циклических кодов с d0 < 5

Пример Построить 31-разрядный код БЧХ, исправляющий три ошибки в кодовой комбинации (т. е. n = 31, S = 3).

Решение:

1. Определим количество контрольных разрядов m и информационных разрядов k.

m £ h S.

Определим параметр h из формулы

n = 2h-1,h = log2(n+1) = log232 = 5,

при этом: m £ h S = 5×3 = 15; k = n-m = 31-15 = 16.

Таким образом, получили (31, 16)-код.

2.Определим параметры образующего полинома:

— количество минимальных многочленов, входящих в образующий

L = S = 3;

— порядок старшего минимального многочлена

r = 3S-1 = 5;

— степень образующего многочлена

b = m £ 15.

1. Выбор образующего многочлена.

Из таблицы для минимальных многочленов для кодов БЧХ ( приложение 4) из колонки 5 (т. к. l = h = 5) выбираем три минимальных многочлена 1, 3 и 5 (т. к. r = 5):

M1(x) =100101;

M2(x) =111101;

M3(x) =110111.

При этом

P(x) = M1(x) ×M2(x) ×M3(x) =1000111110101111=

= x15+ x11 +x10+ x9+ x8+ x7+ x5+ x3 + x2+x+ 1.

4. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 31. Остальные строки матрицы получаем в результате k-кратного циклического сдвига справа налево первой строки матрицы.

000000000000000100011111011111

G(31,16)=000000000000001000111110111110

. . .

100011111011111000000000000000

Строки образующей матрицы представляют собой 16 кодовых комбинации кода БЧХ, а остальные могут быть получены путем суммирования по модулю 2 всевозможных сочетаний строк матрицы.

Декодирование кодов БЧХ

Коды БЧХ представляют собой циклические коды и, следовательно, к ним применимы любые методы декодирования циклических кодов. Открытие кодов БЧХ привело к необходимости поиска новых алгоритмов и методов реализации кодеров и декодеров. Получены существенно лучшие алгоритмы, специально разработанные для кодов БЧХ. Это алгоритмы Питерсона, Бэрлекэмпа и др.

Рассмотрим алгоритм ПГЦ (Питерсона-Горенстейна-Цирлера). Пусть БЧХ код над полем GF(q) длины n и с конструктивным расстоянием d задается порождающим полиномом g(x), который имеет среди своих корней элементы

, — целое число (например 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что . Принятое слово r(x) можно записать как r(x) = c(x) + e(x), где e(x) — полином ошибок. Пусть произошло ошибок на позициях (t максимальное число исправляемых ошибок), значит , а — величины ошибок.

Можно составить j-ый синдром Sj принятого слова r(x):

.

Задача состоит в нахождений числа ошибок u, их позиций

и их значений при известных синдромах Sj.

Предположим, для начала, что u в точности равно t. Запишем (1) в виде системы нелинейных уравнений в явном виде:

Обозначим через

локатор k-ой ошибки, а через величину ошибки, . При этом все Xk различны, так как порядок элемента β равен n, и поэтому при известном Xk можно определить ik как ik = logβXk.

Составим полином локаторов ошибок:

Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на

. Полученное равенство будет справедливо для :

Положим

и подставим в (3). Получится равенство, справедливое для каждого и при всех :

Таким образом для каждого l можно записать свое равенство. Если их просуммировать по l, то получиться равенство, справедливое для каждого

: .

Учитывая (2) и то, что

(то есть

меняется в тех же пределах, что и ранее) получаем систему линейных уравнений:

.

Или в матричной форме

,

Где

Если число ошибок и в самом деле равно t, то система (4) разрешима, и можно найти значения коэффициентов

. Если же число u < t, то определитель матрицы S(t) системы (4) будет равен 0. Это есть признак того, что количество ошибок меньше t. Поэтому необходимо составить систему (4), предполагая число ошибок равным t − 1. Высчитать определитель новой матрицы S(t − 1) и т. д., до тех пор, пока не установим истинное число ошибок.

После этого можно решить систему (4) и получить коэффициенты полинома локаторов ошибок. Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля GF(qm). К ним найти элементы, обратные по умножению, — это локаторы ошибок

. По локаторам можно найти позиции ошибок (ik = logβXk), а значения Yk ошибок из системы (2), приняв t = u. Декодирование завершено.

Источник: https://mirznanii.com/a/113364/kody-bouza-choudkhuri-khokvingema

Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды

Двоичные коды Боуза-Чоудхури-Хоквингема (БЧХ):  Двоичный код БЧХ имеет параметры: п = 2х - 1, к = 2х - lu-t - 1, d =

Код Рида-Соломона. Правило построения кода. Достоинства и недостатки. Применение.

Коды Рида-Соломона были предложены в 1960 году Ирвином Ридом (Irving S. Reed) и Густавом Соломоном (Gustave Solomon), являвшимися сотрудниками Линкольнской лаборатории МТИ.

Коды Рида-Соломона применяются для исправления ошибок во многих системах:

• устройствах памяти (включая магнитные ленты, CD, DVD, штрих-коды, и т.д.);

• беспроводных или мобильных коммуникациях (включая сотовые телефоны, микроволновые каналы и т.д.);

• спутниковых коммуникациях;

• цифровом телевидении / DVB (digital video broadcast);

• скоростных модемах, таких как ADSL, xDSL и т.д.

Кодирование с помощью кода Рида — Соломона может быть реализовано двумя способами: систематическим и несистематическим

При несистематическом кодировании информационное слово умножается на некий неприводимый полином в поле Галуа.

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

Такое кодирование требует большие затраты ресурсов только на извлечение информационных данных, при этом они могут быть без ошибок.

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

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

Кроме того, так как все операции проводятся в поле Галуа, то сами операции кодирования/декодирования требуют много ресурсов и времени. Быстрый алгоритм декодирования, основанный на быстром преобразовании Фурье, выполняется за время порядка .

Преимущество использования кодов Рида-Соломона заключается в том, что вероятность сохранения ошибок в декодированных данных обычно много меньше, чем вероятность ошибок, если коды Рида-Соломона не используются. Это часто называется выигрышем кодирования.

Ричный (15,11) код Рида — Соломона

Пусть . Тогда

Степень равна 4, и . Каждому элементу поля можно сопоставить 4 бита. Информационный многочлен является последовательностью 11 символов из , что эквивалентно 44 битам, а все кодовое слово является набором из 60 бит.

Ричный (7,3) код Рида — Соломона

Пусть . Тогда

Пусть информационный многочлен имеет вид

.

Кодовое слово несистематического кода запишется в виде

что представляет собой последовательность семи восьмеричных символов.

Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды

http://stu.sernam.ru/book_pds.php?id=98

Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды) — в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок. Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием. Частным случаем БЧХ-кодов является код Рида — Соломона.

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

Построение

Для нахождения порождающего полинома необходимо выполнить несколько этапов:

· выбрать q, то есть поле GF(q), над которым будет построен код;

· выбрать длину n кода из условия n = (qm − 1) / s, где m,s — целые положительные числа;

· задать величину d конструктивного расстояния;

1) построить циклотомические классы элемента β = αs поля GF(qm) над полем GF(q), где α —примитивный элемент GF(qm);

2) поскольку каждому такому циклотомическому классу соответствует неприводимый полином над GF(q),корнями которого являются элементы этого и только этого класса, со степенью равной количествуэлементов в классе, то выбрать таким образом, чтобы суммарная длинациклотомических классов была минимальна

3) вычислить порождающий полином , где fi(x) — полином,соответствующий i-ому циклотомическому классу

Пример

Кодирующий многочлен для БЧХ-кода, длина кодовых слов которого , строится так. Находится примитивный многочленминимальной степени такой, что или . Пусть — корень этого многочлена, тогда рассмотрим кодирующий многочлен , где — многочлены минимальной степени, имеющие корнями соответственно .

Построенный кодирующий многочлен производит код с минимальным расстоянием между кодовыми словами, не меньшим , и длиной кодовых слов n [1].

Пример. Нужно построить БЧХ-код с длиной кодовых слов и минимальным расстоянием между кодовыми словами . Степень примитивного многочлена равна и сам он равен . Пусть — его корень, тогда и — также его корни. Минимальным многочленом для будет . Следовательно,

Степень полученного многочлена равна 8, следовательно, построенный БЧХ-код будет -кодом. Слово 1000100 или будет закодировано кодовым словом или 111001100000100.

Синдром

Отыскание синдрома кода БЧХ по принятой последовательности символов может осуществляться путем деления многочлена на минимальные многочлены , задающие порождающиймногочлен двоичного кода БЧХ (5.25). Действительно:

,
,
…………………………..
,

где – остаток от деления многочлена на минимальный многочлен .

Подставив в -е уравнение корень минимального многочлена , имеем

, (5.30)

поскольку . Учитывая (5.27), получим, что -й компонент синдрома .

Код Хэмминга

http://info.sernam.ru/book_codb.php?id=28

http://studopedia.ru/3_97798_kodi-hemminga.html

Код Хэмминга, являющийся групповым (n,k) кодом, с минимальным расстоянием d=3 позволяет обнаруживать и исправлять однократные ошибки. Для построения кода Хэмминга используется матрица H. , где Ak- транспонированная подматрица, En-k — единичная подматрица порядка n-k.

Если Х — исходная последовательность, то произведение Х·Н=0. Пусть E— вектор ошибок. Тогда (Х+Е)·Н = Х·Н+Е·Н = 0+Е·Н=E·H — синдром или корректор, который позволяет обнаружить и исправить ошибки. Контрольные символы e1 ,e2 ,…,er образуются из информационных символов, путем линейной комбинации , где аj={0,1} — коэффициенты, взятые из подматрицы A матрицы H.

Рассмотрим Построение кода Хэмминга для k=4 символам. Число контрольных символов r=n-k можно определить по неравенству Хэмминга для однократной ошибки. Но так, как нам известно, только исходное число символов k, то проще вычислить по эмпирической формуле

, (5.2)

где [.] — означает округление до большего ближайшего целого значения. Вычислим для k=4 . Получим код (n,k)=(7,4); n=7; k=4; r=n-k=3; d=3. Построим матрицу H.

Контрольные символы ej определим по формуле . Например, . Для простоты оставляем только слагаемые с единичными коэффициентами. В результате получим систему линейных уравнений, с помощью которых вычисляются контрольные разряды. Каждый контрольный разряд является как бы дополнением для определенных информационных разрядов для проверки на четность.

При декодировании вычисляем корректор K=k4k2k1

Если корректор равен нулю, следовательно, ошибок нет. Если корректор не равен нулю, то местоположение вектор-столбца матрицы H, совпадающего с вычисленным корректором, указывает место ошибки. При передаче может возникнуть двойная и более ошибка.

Корректор также не будет равен нулю. В этом случае произойдет исправление случайного символа и нами будет принят неверный код. Для исключения такого автоматического исправления вводится еще один символ для проверки всей комбинации на четность. Кодовое расстояние d=4.

Тогда матрица H будет иметь вид

Матрица проверок для (n+1, k) – кода Хэмминга с dmin=4 получается из матрицы проверок (n, k) – кода с dmin=3 путем введения дополнительной строки из (n+1)-ой единицы.

Так как размерность матрицы проверок кода с dmin=4 должна быть равна , то к каждой строке матрицы проверок кода с dmin=3, необходимо добавить один нулевой элемент для того, чтобы не нарушить введенные ранее проверки. Матрица проверок для (n+1, k) – кода dmin=4 имеет вид:

,

где H(n,k) = матрица проверок исходного кода с dmin=3.

Применение

Код Хэмминга используется в некоторых прикладных программах в области хранения данных, особенно в RAID 2; кроме того, метод Хэмминга давно применяется в памяти типа ECC и позволяет «на лету» исправлять однократные и обнаруживать двукратные ошибки.

Просмотров 1345 Эта страница нарушает авторские права

Источник: https://allrefrs.ru/1-27634.html

Циклический код Боуза — Чоудхури — Хоквингема

Двоичные коды Боуза-Чоудхури-Хоквингема (БЧХ):  Двоичный код БЧХ имеет параметры: п = 2х - 1, к = 2х - lu-t - 1, d =

     Код Боуза-Чоудхури-Хоквингема (БЧХ) относятся к циклическим помехоустойчивым кодам. Циклические коды широко применяются при построении устройств вычислительной техники и вычислительных сетей.

    Определим некоторые понятия, встречающиеся при использовании циклических кодов.

    CRC (Cyclic redundancy check) — код циклического контроля. Термин используется только для помехоустойчивых циклических кодов, обнаруживающих ошибки. Буквами CRC также указываются разряды (байты ), отводимые в формате под контрольные (избыточные) символы, формируемые при передаче (записи).При приеме (чтении) с помощью этих символов определяется отсутствие или наличие ошибки.

    EDC (Error Diagnostic Codes) — помехоустойчивые коды, обнаруживающие ошибки. Термин используется для всех помехоустойчивых кодов, обнаруживающих ошибки. Буквами EDC также указываются разряды (байты), отводимые в формате под контрольные символы, формируемые при передаче (записи) информации. При приеме (чтении) с помощью этих символов определяется наличие или отсутствие ошибки.

    ECC ( Error Correction Codes) — помехоустойчивые коды, исправляющие ошибки. Буквами ECC указываются также разряды (байты), отводимые в формате для контрольных символов, формируемых при передаче (записи). При приеме (чтении) с помощью этих символов определяется наличие ошибки и проводится исправление.

    При использовании циклических кодов все контрольные символы принято размещать в конце кодовой комбинации после информационных символов.

    Приведем некоторые примеры применения циклических кодов.

    В накопителях на гибких магнитных дисках все операции записи данных сопровождаются формированием и записью в конце поля после 512 информационных байт (сектор) 2 байт CRC.

    В накопителях на жестких магнитных дисках (НЖМД) используются циклические коды, исправляющие ошибки (ECC). Фирмы-производители НЖДМ включают схемы формирования ECC и исправления ошибок в контроллеры жестких дисков.

Поскольку в настоящее время используются НЖДМ со встроенными контроллерами, то пользователю и не сообщается о конкретном используемом коде.

Например, в ряде контроллеров для сектора длиной 512 байт формируется ECC длиной 7 байт.

    В CD-ROM для обеспечения высокой надежности в формат файловой системы по стандарту ISO 9660 (High Sierra) введены поля EDC длиной 4 байта и ECC длиной 276 байт для информационного поля длиной 2048 байт. Используется код Рида-Соломона с перемежением- CIRS-Cross Interleave Reed Solomon. Этот же код используется в ряде устройств архивного хранения информации на магнитной ленте (стримерах).

    В универсальной последовательной шине USB- Universal Serial Bus — для обнаружения ошибок передачи каждый пакет имеет поля CRC, позволяющие обнаруживать все однократные и двухкратные битовые ошибки.

    В данной лабораторной работе изучаются циклические коды Боуза-Чоудхури-Хоквингема, замечательной особенностью данного кода является то, что при заданном числе информационных символов и заданной корректирующей способности требуется минимальное  число контрольных символов. Этот код включен в формат POCSAG систем поискового радиовызова.

    Процедура кодирования и декодирования для БЧХ- кода аналогична процедуре кодирования всех циклических кодов.  

Цель данной лабораторной работы: научиться определять число информационных и контрольных символов для заданного количества букв алфавита и заданного количества исправляемых ошибок, находить образующий многочлен для конкретных условий применения, кодировать и декодировать в БЧХ-коде символы ASCII-таблицы, экспериментальная проверка корректирующих свойств БЧХ-кода.

    В теории кодирования используется ряд базовых определений, необxодимых для эффективного построения всевозможных кодовых комбинаций. Так как в различной литературе одни и те же понятия обозначаются различными символами, примем ряд соглашений и дадим определения тем символам и понятиям, которые будут использованы в данной работе.

    Весом W(А) кодовой комбинации A a4,a3, a2,a1 называется число, содержащихся в ней двоичных единиц.

    Кодовое расстояние d или расстояние Хэмминга-расстояние между ближайшими кодовыми комбинациями. Оно определяется числом позиций, в которых их двоичные знаки не совпадают. Это значит, что кодовое расстояние между двоичными комбинациями X и Y равно весу W(Z) некоторой третьей комбинации Z, получаемой поразрядным сложением по модулю 2 этих комбинаций т.е. d=W(Z)=W(XЕY).

Например: Х=100011100001011; Y=100101000110011;

Z=XЕY

X=100011100001011

Е

Y=100101000110011

                Z= 000110100111000, т.о d=6.

    При описании циклических кодов n-разрядные кодовые комбинации представляются в виде многочленов c фиктивной переменной X. Показатели степени у X соответствуют номерам разрядов (начиная с нулевого ), при этом наименьшему разряду числа соответствует фиктивная переменная X0=1. Для двоичных циклических кодов коэффициентами при X ,будут цифры  0 и 1.

    Например, 01011=0*X4+1*X3+0*X2+1*X+1, поскольку члены с нулевыми коэффициентами при записи многочлена опускаются, получим  01011=X3+X+1. Теперь действия над кодовыми комбинациями сводятся к действиям над многочленами.

    Для многочленов характерны следующие арифметические действия: cложение, деление и умножение многочленов. Рассмотрим эти операции на примерах. Для удобства проведения арифметических операций многочлены запишем в двоичном виде.

    Сложение при действиях над многочленами осуществляется по модулю два.

Пример:   10011

              Е

           10001

           00010.

    Умножение можно выполнять по обычным правилам, только производя суммирование по модулю два.

    Рассмотрим пример: 10011×10001

                      10011

                    x 10001

                      10011

                     00000

              Е     00000

                   00000

                  10011   

                  100100011

    Для программной реализации можно воспользовать следующий алгоритм:

    Шаг 1. Исследовать младший разряд множителя, если он равен 1, то сложить множимое с результатом  по модулю два и перейти к шагу 2; если он равен 0, перейти к шагу 2.

    Шаг 2. Сдвинуть множимое на один разряд влево.

    Шаг 3. Выполнить действия шага 1 для следующего по старшенству разряда множителя

    Умножение заканчивается после того, как будет выполнено действие шага 1 для самого старшего разряда множителя.

    Рассмотрим предыдущий пример: перемножим два многочлена: 10011×10001

    Шаг 1. Исследуем младший разряд множителя, так как он равен единице, имеем

                          10011

                     x   10001

                          10011

  Шаг 2. Сдвигаем множимое на один разряд влево.

                         10011

                      x 10001

                         10011                   

                       10011

   Шаг 3. Так как следующий по старшинству разряд множителя равен нулю, то суммирование не производим , а сдвигаем множимое еще на один разряд влево.

                         10011

                      x 10001

                         10011

                     10011

Шаг 4. Так как следующий по старшинству разряд множителя равен нулю, то суммирование не производим , а сдвигаем множимое еще на один разряд влево.

                         10011

                      x 10001

                         10011

                   10011

  Шаг 5. Так как следующий по старшинству разряд множителя равен нулю, сдвигаем множимое еще на один разряд влево.

                         10011

                      x 10001

                         10011

                 10011

   Шаг 6. Так как старший разряд множителя равен единице, то складываем множимое с результатом по модулю два

                         10011

                      x 10001

                         10011

              Е10011       

                 100100011- искомый результат.

       Деление многочленов как и умножение заменено многократным сложением по модулю два. Рассмотрим деление многочлена 10011 на многочлен 11.

    Шаг 1. Под старшим разрядом делимого, в котором содержится единица записываем делитель и складываем по модулю два.

                    10011   |11    

                 Е11          1

                    01

     Шаг 2. К полученному остатку сносим следующий разряд делимого, под полученным числом записываем делитель и вновь складываем по модулю 2.

                    10011   |11    

                 Е11          11

                    010

                   Е11

                      01

    Шаг 3. К полученному остатку сносим следующий разряд делимого, под полученным числом записываем делитель и вновь складываем по модулю 2.

                    10011   |11    

                 Е11          111

                    010

                   Е11

                      011

                     Е11

                        00

    Шаг 4. К полученному остатку сносим следующий разряд делимого, под полученным числом записываем делитель и вновь складываем по модулю 2.

                    10011   |11    

                 Е11          111

                    010

                   Е11

                      011

                     Е11

                        001

                       Е11

                          10 — остаток

    В результате деления многочлена 10011 на многочлен 11 получаем частное 1111 и остаток 10.  

    Число информационных символов m-количество разрядов, необходимое для передачи сообщения без использования корректирующих символов.

     Число контрольных символов k-количество разрядов, необходимое в данном коде для обеспечения заданной помехоустойчивости.

     Длина кодовой комбинации n — комбинация из контрольных и информационных символов, где n = m + k.

    Неприводимый минимальный многочлен M(X)-многочлен, делящийся без остатка на себя и на единицу. Неприводимые минимальные многочлены в теории циклических кодов используются для получения образующих многочленов.

    Образующий многочлен K(X)-многочлен, при помощи которого происходит построение того или иного кода с заданными помехоустойчивыми параметрами. Образующий многочлен может быть равен неприводимому минимальному многочлену или являться их произведением.

Пример: К(X) = M(X) = 101111 = X5+X3+X2+X+1;

К(X) = M1(X)*M3(X) = 10011*11111 = 111010001 = X8+X7+X6+X4+1.

   В теории циклических кодов неприводимые минимальные  многочлены определены и сведены в таблицу минимальных неприводимых многочленов.

    Число минимальных многочленов V — минимальное количество неприводимых многочленов, необходимое для построения образующего многочлена.

     Образующая матрица C(n,m)- матрица, при помощи которой происходит построение циклического кода. Образующая матрица получается в результате m- кратного циклического сдвига кодовой комбинации, соответствующей первой строке образующей матрицы.  Первая строка образующей матрицы получается путем добавления слева от K(X) такого числа нулей, чтобы общая длина кодовой комбинации была равна n.

Например, образующий многочлен имеет вид  K(X)=111010001=X8+X7+X6+X4+1 при n=15 и m=7. Тогда первая строка образующей матрицы примет вид:  000000111010001, а вся матрица:

0 0 0 0 0 0 1 1 1 0 1 0 0 0 1

0 0 0 0 0 1 1 1 0 1 0 0 0 1 0

0 0 0 0 1 1 1 0 1 0 0 0 1 0 0

0 0 0 1 1 1 0 1 0 0 0 1 0 0 0

0 0 1 1 1 0 1 0 0 0 1 0 0 0 0

0 1 1 1 0 1 0 0 0 1 0 0 0 0 0

1 1 1 0 1 0 0 0 1 0 0 0 0 0 0

     Большинство циклических кодов используют один алгоритм построения помехоустойчивых кодовых комбинаций, а отличаются лишь методикой выбора образующего многочлена.

     В БЧХ-коде построение образующего многочлена, в основном, зависит от двух параметров: от длины кодового слова n=m+k и от числа исправляемых ошибок S.

    Особенностью кода является,   то что  для исправления числа ошибок S>=2 еще недостаточно условия, что между комбинациями кода минимальное кодовое расстояние dmin=2*S+1. Необходимо также, чтобы длина кода n удовлетворяла условию

n = 2h — 1,                                                    (1)

где h -любое целое число.

При этом n всегда будет нечетным числом и принимать значения: 1,3,7,15,31,63,127..и.т.д, т.е не все m могут быть заданы пользователем.

    Выбранная по формуле (1) величина n определяет число контрольных символов k.

k S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

   0 1 0 0 0 0 0 1 1 0 0 1 1 1 0 | 1 1 1 0 1 0 0 0 1

   Е1 1 1 0 1 0 0 0 1                   1 1 0 1 0 0

         1 1 0 1 0 1 1 1 0

      Е1 1 1 0 1 0 0 0 1

               1 1 1 1 1 1 1 1 1

            Е1 1 1 0 1 0 0 0 1

                        1 0 1 1 1 0 1 W > S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

   1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 | 1 1 1 0 1 0 0 0 1

Е1 1 1 0 1 0 0 0 1                     1 1 0 1 0 0 1

      1 1 0 1 0 1 1 1 0

   Е1 1 1 0 1 0 0 0 1

            1 1 1 1 1 1 1 1 1

        Е1 1 1 0 1 0 0 0 1

                     1 0 1 1 1 0 1 0 0

                  Е1 1 1 0 1 0 0 0 1

                         1 0 1 0 0 1 0 1W > S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

   0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 | 1 1 1 0 1 0 0 0 1

               Е1 1 1 0 1 0 0 0 1      1 0

                        1 0 0 1 1 0 1 1W > S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

   0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 | 1 1 1 0 1 0 0 0 1

            Е1 1 1 0 1 0 0 0 1         1 0 1

                      1 0 0 1 1 0 1 1 0

                  Е1 1 1 0 1 0 0 0 1

                        1 1 1 0 0 1 1 1 W > S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

   0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 | 1 1 1 0 1 0 0 0 1

         Е1 1 1 0 1 0 0 0 1               1 0 1 1

                   1 0 0 1 1 0 1 1 0

                Е1 1 1 0 1 0 0 0 1

                      1 1 1 0 0 1 1 1 0 

                  Е1 1 1 0 1 0 0 0 1

                                   1 1 1 1 1 W > S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

   0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 | 1 1 1 0 1 0 0 0 1

      Е1 1 1 0 1 0 0 0 1               1 0 1 1 0

                   1 0 0 1 1 0 1 1 0

                Е1 1 1 0 1 0 0 0 1

                      1 1 1 0 0 1 1 1 0 

                  Е1 1 1 0 1 0 0 0 1

                                   1 1 1 1 1 W > S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

   0 1 1 0 0 1 1 1 0 0 1 0 0 0 0 | 1 1 1 0 1 0 0 0 1

   Е1 1 1 0 1 0 0 0 1                   1 0 1 1 0 0

             1 0 0 1 1 0 1 1 0

         Е1 1 1 0 1 0 0 0 1

               1 1 1 0 0 1 1 1 0 

            Е1 1 1 0 1 0 0 0 1

                            1 1 1 1 1 0 0 W > S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

    1 1 0 0 1 1 1 0 0 1 0 0 0 0 0 | 1 1 1 0 1 0 0 0 1

Е1 1 1 0 1 0 0 0 1                      1 0 1 0 0 0

          1 0 0 1 1 0 1 1 0

       Е1 1 1 0 1 0 0 0 1

             1 1 1 0 0 1 1 1 0 

          Е1 1 1 0 1 0 0 0 1

                          1 1 1 1 1 0 0 0 W > S, далее в соответствии с процедурой декодирования сдвигаем  влево пока не получим вариант, удовлетворяющий условию W = S.

   1 0 0 1 1 1 0 0 1 0 0 0 0 0 1 | 1 1 1 0 1 0 0 0 1

Е1 1 1 0 1 0 0 0 1                      1 1 0 0 0 0 0

      1 1 1 0 1 0 0 0 0

   Е1 1 1 0 1 0 0 0 1

                              1 0 0 0 0 1 W = S, следовательно

   1 0 0 1 1 1 0 0 1 0 0 0 0 0 1

Е                           1 0 0 0 0 1

   1 0 0 1 1 1 0 0 1 1 0 0 0 0 0

    В данном примере пришлось проводить   двенадцати кратный сдвиг влево.

Далее, в соответствии с алгоритмом декодирования,   проводим 12-кратный циклический сдвиг вправо комбинации, полученной в результате сложения по модулю два последнего делимого и последниго остатка, или    3-кратный сдвиг влево той же комбинации. Полученная после соответствующего числа циклических сдвигов комбинация, не содержит ошибок 111001100000100

     Теоретически БЧХ- коды могут исправлять произвольное количество ошибок, однако с ростом кратности ошибки значительно возрастает длина кода, что неизбежно ведет к уменьшению скорости передачи и усложнению приемно-передающей аппаратуры.

Источник: http://labs.vt.tpu.ru/B4H/theory.php

Scicenter1
Добавить комментарий