Код Боуза — Чоудхури — Хоквингема — Национальная библиотека им. Баумана. Материал из Национальной библиотеки им. Баумана. Последнее изменение этой страницы: 2. Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием. Главной задачей является построение кода с заданным кодовым расстоянием (заданными корректирующими свойствами). Построим циклический линейный код над конечным полем  Fq.

Коды Боуза-Чоудхури-Хоквингема бчх класс циклических кодов Пример Построить 15-разрядный код БЧХ, исправляющий две ошибки в кодовой. Код Боуза-Чоудхури-Хоквингема (БЧХ) относятся к циклическим помехоустойчивым кодам. Приведем некоторые примеры применения циклических кодов. 7.3), с помощью которых образующий полином кода БЧХ находится как их Для конкретизации приведенной методики рассмотрим примеры. Код примитивный: 15=24. Коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс циклических кодов. Пример Построить 15-разрядный код БЧХ, исправляющий две ошибки в кодовой комбинации (т.

Также можно задать код при помощи некоторых выделенных корней этого полинома. Рассмотрим любое  . Следовательно для  . Для них можно построить  HOK: g=HOK(gi..,gl). Пример Пример: Примитивный 2- ичный (1. Пусть q=2 . Они принадлежат двум циклотомическим классам над полем GF(2) .

Тогда полином. g(x)=f. Пример Пример: 1.

Рида — Соломона). Пусть n=q. Тогда. Можно сказать, что такой код работает с полубайтами информации.

Проверочная матрица БЧХ- кода. Построим проверочную матрицу для БЧХ- кода. Рассмотрим для  n W(x. Разложим определитель по последней строке.

Алгоритм Питерсона- Горештейна- Цирлера. Пусть  e. Рассмотрим вектор ошибки  e.

Согласно этому принципу строятся коды Боуза-Чоудхури-Хоквингема (коды БЧХ). Для примера построим порождающий многочлен для кода БЧХ, исправ-ляющего две ошибки (t = 2). Главной задачей является построение кода с заданным кодовым расстоянием (заданными корректирующими свойствами). Построим циклический линейный код над конечным полем., который задается следующими параметрами: - длина кода, - конструктивное расстояние. Эти коды получили названия кодов Боуза-Чоудхури-Хоккенгема или БЧХ-кодов (BCH codes).

Определение «Определение - Локатор ошибки»Локатор ошибки  . Множество локаторов ошибок однозначно определяет все позиции ошибок. Определение «Определение - Многочлен локаторов ошибки»Многочлен вида  . Построим проверочную матрицу.

Тогда. y. 0+y. 1. Возьмем любое  Sb+j. Представим полином ошибки в сокращенном виде. Необходимо показать, что матрица вида не вырождена и равна. При этом известно  .

Подставим  . Домножим на  ei. Проверим поэлементно.

Sij=. Процедура Ченя: L=O(nt) . Для двоичного кода вычисление не требуется, так как вариант ошибки только один. Деление многочленов: L=O(n. Дж, Слоэн Н. Теория кодов, исправляющих ошибки: Пер.

Коды Боуза- Чоудхури- Хоквингема. РЕФЕРАТПо курсу “Теория информации и кодирования”на тему. Коды БЧХ строятся по заданной длине кодового слова n и числа исправляемых ошибок S , при этом количество информационных разрядов k не известно пока не выбран определяющий полином. Рассмотрим процедуру кодирования с использованием кода БЧХ на конкретных примерах. Пример Построить 1.

БЧХ, исправляющий две ошибки в кодовой комбинации (т. Определим количество контрольныхm и информационных разрядов km . Таким образом, получили (1. Определим параметры образующего полинома: - количество минимальных многочленов, входящих в образующий L = S = 2; - порядок старшего (все минимальные - нечетные) минимального многочлена r = 2.

S- 1 = 3; - степень образующего многочленаb = m . Выбор образующего многочлена. Из таблицы для минимальных многочленов для кодов БЧХ (см. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 1. Остальные строки матрицы получаем в результате k- кратного циклического сдвига справа налево первой строки матрицы. Строки образующей матрицы представляют собой 7 кодовых комбинаций кода БЧХ, а остальные могут быть получены путем суммирования по модулю 2 всевозможных сочетаний строк матрицы.

Процедура декодирования, обнаружения и исправления ошибок в принятой кодовой комбинации такая же, как и для циклических кодов с d. Пример Построить 3. БЧХ, исправляющий три ошибки в кодовой комбинации (т. Определим количество контрольных разрядов m и информационных разрядов k.

Таким образом, получили (3. Определим параметры образующего полинома: - количество минимальных многочленов, входящих в образующий L = S = 3; порядок старшего минимального многочленаr = 3. S- 1 = 5; степень образующего многочлена b = m . Из таблицы для минимальных многочленов для кодов БЧХ ( приложение 4) из колонки 5 (т. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 3. Остальные строки матрицы получаем в результате k- кратного циклического сдвига справа налево первой строки матрицы.

G(3. 1,1. 6)=0. 00. Автосигнализация Magicar Инструкция Автосигнализация Magicar здесь. Открытие кодов БЧХ привело к необходимости поиска новых алгоритмов и методов реализации кодеров и декодеров. Получены существенно лучшие алгоритмы, специально разработанные для кодов БЧХ. Это алгоритмы Питерсона, Бэрлекэмпа и др.

Рассмотрим алгоритм ПГЦ (Питерсона- Горенстейна- Цирлера). Пусть БЧХ код над полем 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 различны, так как порядок элемента . Помножим обе части этого полинома на . Полученное равенство будет справедливо для: Положим и подставим в (3). Получится равенство, справедливое для каждого и при всех : Таким образом для каждого l можно записать свое равенство. Если их просуммировать по l, то получиться равенство, справедливое для каждого. Учитывая (2) и то, что (то есть меняется в тех же пределах, что и ранее) получаем систему линейных уравнений. Или в матричной форме,Где.

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

Поэтому необходимо составить систему (4), предполагая число ошибок равным t . Высчитать определитель новой матрицы S(t . Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля GF(qm). К ним найти элементы, обратные по умножению, — это локаторы ошибок . По локаторам можно найти позиции ошибок (ik = log.

Декодирование завершено. Коды Рида–Соломона. Широко используемым подмножеством кодов БЧХ являются коды Рида- Соломона, которые позволяют исправлять пакеты ошибок. Пакет ошибок длины b представляет собой последовательность из таких b ошибочных символов, что первый и последний из них отличны от нуля.

Существуют классы кодов Рида- Соломона, позволяющие исправлять многократные пакеты ошибок. Коды Рида- Соломона широко используются в устройствах цифровой записи звука, в том числе на компакт- диски. Данные, состоящие из отсчетов объединяются в кадр, представляющий кодовое слово. Кадры разбиваются на блоки по 8 бит. Часть блоков являются контрольными.

Обычно 1 кадр (кодовое слово) = 3. Сигнальные символы это вспомогательные данные, облегчающие декодирование: служебные сигналы, сигналы синхронизации и т. При передаче данных производится перемежение (изменение порядка следования по длине носителя и во времени) блоков с различным сдвигом во времени, в результате чего расчленяются сдвоенные ошибки, что облегчает их локализацию и коррекцию. При этом используются коды Рида- Соломона с минимальным кодовым расстоянием d. Сверточные коды. Кроме рассмотренных корректирующих кодов используются так называемые сверточные коды, контрольные биты, в которых формируются непрерывно из информационных и контрольных бит смежных блоков. Выводы. Таким образом, в результате написания реферата, пришли к выводу, что коды Боуза- Чоудхури- Хоквингхема – это широкий класс циклических кодов, способных исправлять многократные ошибки.

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

Список использованной литературы. Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and practice of error control codes. Дмитриев В. И. Прикладная теория информации: Учебник для вузов.

М.: Высшая школа , 1. Колесник В. Д., Полтырев Г. Ш. Курс теории информации. Теория информации.

Учебник для вузов Изд- во ПИТЕР, 2. Коды, исправляющие ошибки. Keycheck Для W8.1. Семенюк В. Экономное кодирование дискретной информации. Уэлдон, Коды, исправляющие ошибки, Москва, “Мир”, 1.