Что такое синдром бчх коды

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

Формальное описание[править | править код]

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

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

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

Число проверочных символов равно степени , число информационных символов , величина называется конструктивным расстоянием БЧХ-кода. Если , то код называется примитивным, иначе — непримитивным.

Так же, как и для циклического кода, кодовый полином может быть получен из информационного полинома степени не больше , путём перемножения и :

Построение[править | править код]

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

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

Примеры кодов[править | править код]

Примитивный двоичный (15, 7, 5) код[править | править код]

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

имеет в качестве корней элементы и является порождающим полиномом БЧХ-кода с параметрами .

16-ричный (15, 11, 5) код (код Рида — Соломона)[править | править код]

Пусть , и — примитивный элемент . Тогда

Каждый элемент поля можно сопоставить 4 битам, поэтому одно кодовое слово эквивалентно 60 = 15 × 4 битам, таким образом набору из 44 битов ставится в соответствие набор из 60 битов. Можно сказать, что такой код работает с полубайтами информации.

Кодирование[править | править код]

Для кодирования кодами БЧХ применяются те же методы, что и для кодирования циклическими кодами.

Методы декодирования[править | править код]

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

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

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

Синдромы определены как значения принятого полинома в нулях порождающего многочлена кода:

где .

Для нахождения множества локаторов ошибок введём в рассмотрение многочлен локаторов ошибок

корни которого равны обратным величинам локаторов ошибок. Тогда справедливо следующее соотношение между коэффициентами многочлена локаторов ошибок и синдромами[5]:

Известны следующие методы для решения этой системы уравнений относительно коэффициентов многочлена локаторов ошибок (ключевая система уравнений).

Алгоритм Берлекемпа — Мэсси[править | править код]

Этот алгоритм лучше всего рассматривать как итеративный процесс построения минимального регистра (сдвига) с обратной связью, генерирующего известную последовательность синдромов . Его фактическая цель — построить полином наименьшей степени, удовлетворяющему уравнению

Решение этого уравнения эквивалентно условию

Итеративный процесс построения такого многочлена и есть Алгоритм Берлекемпа — Мэсси.

Евклидов алгоритм[править | править код]

В основе этого метода лежит широко известный алгоритм Евклида по нахождению наибольшего общего делителя двух чисел (НОД), только в данном случае ищем НОД не двух чисел, а двух полиномов. Обозначим полином значений ошибок как , где синдромный полином равен . Из системы уравнений следует, что . Задача по сути сводится к тому чтобы определить удовлетворяющего последнему уравнению и при этом степени не выше . По сути такое решение и будет давать расширенный алгоритм Евклида, примененный к многочленам и , где . Если на -м шаге расширенный алгоритм Евклида выдает решение , такое что , то , и . При этом найденный полином дальше не принимает участия в декодировании (он ищется только как вспомогательный). Таким образом будет найден полином локаторов ошибок .

Прямое решение (алгоритм Питерсона — Горенстейна — Цирлера, ПГЦ)[править | править код]

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

Можно составить -й синдром принятого слова :

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

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

Обозначим через локатор -й ошибки, а через — величину ошибки, . При этом все различны, так как порядок элемента равен , и поэтому при известном можно определить как .

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

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

Если подставить сюда , то получится равенство, справедливое для каждого и при всех :

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

Поскольку (то есть, меняется в тех же пределах, что и ранее), система уравнений для синдромов преобразуется в систему линейных уравнений:

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

где

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

Поиск Ченя[править | править код]

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

Алгоритм Форни[править | править код]

Общая схема декодирования БХЧ кодов (алгоритм Форни)

По локаторам можно найти позиции ошибок (), а значения ошибок из системы для синдромов, приняв . Декодирование завершено.

См. также[править | править код]

Обнаружение и исправление ошибок
Конечное поле
Многочлен над конечным полем
Матрица Вандермонда
Линейный код
Циклический код
Код Рида — Соломона
Алгоритм Евклида

Примечания[править | править код]

Литература[править | править код]

Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.
Сагалович Ю. Л. Введение в алгебраические коды — М.: МФТИ, 2007. — 262 с. — ISBN 978-5-7417-0191-1
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. — М.: Техносфера, 2005. — 320 с. — ISBN 5-94836-035-0.

Источник

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

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

Контроль целостности данных и исправление ошибок — важные задачи на многих уровнях работы с информацией (в частности, физическом, канальном, транспортном уровнях сетевой модели OSI) в связи с тем, что в процессе хранения данных и передачи информации по сетям связи неизбежно возникают ошибки.

В системах связи возможны несколько стратегий борьбы с ошибками:

обнаружение ошибок в блоках данных и автоматический запрос повторной передачи[⇨] повреждённых блоков — этот подход применяется, в основном, на канальном и транспортном уровнях;
обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
прямая коррекция ошибок (англ. forward error correction) применяется на физическом уровне.

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

Коды обнаружения ошибок (которые могут только установить факт ошибки) принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить бо́льшее число ошибок, чем был способен исправить). Коды, исправляющие ошибки, применяются в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам, а также в системах хранения информации, в том числе магнитных и оптических. Коды, обнаруживающие ошибки, применяются в сетевых протоколах различных уровней.

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

Блоковые коды[править | править код]

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

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

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

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

Линейные коды общего вида[править | править код]

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

Это значит, что операция кодирования соответствует умножению исходного -битного вектора на невырожденную матрицу , называемую порождающей матрицей.

Для ортогонального по отношению к подпространства и матрицы , задающей базис этого подпространства, и для любого вектора справедливо:

Минимальное расстояние и корректирующая способность[править | править код]

Расстоянием Хэмминга (метрикой Хэмминга) между двумя кодовыми словами и называется количество отличных бит на соответствующих позициях:

Минимальное расстояние Хэмминга является важной характеристикой линейного блокового кода. Она показывает, насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

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

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

Например, при наличии всего двух кодовых слов и с расстоянием Хэмминга между ними, равным 3, ошибка в одном бите слова может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову , чем к . Но если каналом были внесены ошибки в двух битах (в которых отличалось от ), то результат ошибочной передачи окажется ближе к , чем , и декодер примет решение, что передавалось слово .

Коды Хэмминга[править | править код]

Коды Хэмминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хэмминга может быть представлен в таком виде, что синдром:

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

Общий метод декодирования линейных кодов[править | править код]

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

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

Линейные циклические коды[править | править код]

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

Циклическим кодом является линейный код, обладающий следующим свойством: если является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово представляется в виде полинома . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на по модулю .

Чаще всего используются двоичные циклические коды (то есть могут принимать значения 0 или 1).

Порождающий многочлен[править | править код]

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему (генераторному) многочлену . Порождающий многочлен является делителем .

С помощью порождающего многочлена осуществляется кодирование циклическим кодом. В частности:

Коды CRC[править | править код]

Коды CRC (англ. cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путём деления на . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид многочлена задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

Коды БЧХ[править | править код]

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

Коды коррекции ошибок Рида — Соломона[править | править код]

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

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов[править | править код]

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Свёрточные коды[править | править код]

Свёрточный кодер ()

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

Кодирование свёрточным кодом производится с помощью регистра сдвига, отводы от которого суммируются по модулю два. Таких сумм может быть две (чаще всего) или больше.

Декодирование свёрточных кодов, как правило, производится по алгоритму Витерби, который пытается восстановить переданную последовательность согласно критерию максимального правдоподобия.

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование. Итеративное декодирование[править | править код]

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

Например, популярной является следующая конструкция: данные кодируются кодом Рида — Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).

Сетевое кодирование[править | править код]

Оценка эффективности кодов[править | править код]

Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).

Граница Хэмминга и совершенные коды[править | править код]

Пусть имеется двоичный блоковый код с корректирующей способностью . Тогда справедливо неравенство (называемое границей Хэмминга):

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

Энергетический выигрыш[править | править код]

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

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

Автоматический запрос повторной передачи[править | править код]

Системы с автоматическим запросом повторной передачи (англ. Automatic Repeat Request, ARQ) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Идея запроса ARQ с остановками (англ. stop-and-wait ARQ) заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем, как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Для метода непрерывного запроса ARQ с возвратом (continuous ARQ with pullback) необходим полнодуплексный канал. Передача данных от передатчика к приемнику производится одновременно. В случае ошибки передача возобновляется, начиная с ошибочного блока (то есть передается ошибочный блок и все последующие).

При использовании метода непрерывного запроса ARQ с выборочным повторении (continuous ARQ with selective repeat) осуществляется передача только ошибочно принятых блоков данных.

Литература[править | править код]

Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.

Источник