Цифровой корректор ошибок

		Обноружение ошибок
		Исправление ошибок
		Коррекция ошибок
		Назад

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

Синдром	001	010	011	100	101	110	111
Конфигурация ошибок	0000001	0000010	0000100	0001000	0010000	0100000	1000000
Ошибка в символе	m1	m2	i4	m1	i1	i3	i2

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

Введение

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

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

Этот путь привел меня к вопросу, а что я уже могу самостоятельно делать без книжных «костылей», имея перед собой только чистый лист бумаги и карандаш с ластиком? Оказалось совсем немного и не совсем то, что было нужно. Пройден был сложный путь бессистемного самообразования. Вопрос был такой. Могу ли я построить и объяснить, прежде всего себе, работу кода, обнаруживающего и исправляющего ошибки, например, код Хемминга, (7, 4)-код?

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

Информационная безопасность. Коды, шифры, стегосообщения

Информационное взаимодействие путем обмена сообщениями его участников должно обеспечиваться защитой на разных уровнях и разнообразными средствами как аппаратными так и программными. Эти средства разрабатываются, проектируются и создаются в рамках определенных теорий (см. рис.А) и технологий, принятых международными договоренностями об OSI/ISO моделях.

Защита информации в информационных телекоммуникационных системах (ИТКС) становится практически основной проблемой при решении задач управления, как в масштабе отдельной личности – пользователя, так и для фирм, объединений, ведомств и государства в целом. Из всех аспектов защиты ИТКС в этой статье будем рассматривать защиту информации при ее добывании, обработке, хранении и передаче в системах связи.

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

Рисунок А – Схема основных направлений и взаимосвязи теорий, направленных на решение задач защиты информационного взаимодействия

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

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

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

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

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

Поскольку роль сторон переменчива оба этих устройства объединяют в одно и называют сокращенно кодек (кодер/декодер), и устанавливают на обоих концах канала. Дальше, раз есть слова, есть и алфавит. Алфавит — это два символа {0, 1}, в технике массово используются блоковые двоичные коды. Алфавит естественного языка (ЕЯ) — множество символов — букв, заменяющих при письме звуки устной речи. Здесь не будем углубляться в иероглифическую письменность в слоговое или узелковое письмо.

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

Ричард Хемминг, наверное, раньше других понял, что если избыточность не устранять, а разумно организовать, то ее можно использовать в системах связи для обнаружения ошибок и автоматического их исправления в кодовых словах передаваемого текста. Он понял, что все 128 семиразрядных двоичных слов могут использоваться для обнаружения ошибок в кодовых словах, которые образуют код — подмножество из 16 семиразрядных двоичных слов. Это была гениальная догадка.

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

Построение (7, 4)-кода Хемминга

Вернемся к Хеммингу. Слова (7, 4)-кода образованы из 7 разрядов С j =

, j = 0(1)15, 4-информационные и 3-проверочные символа, т.е. по существу избыточные, так как они не несут информации сообщения. Эти три проверочных разряда удалось представить линейными функциями 4-х информационных символов в каждом слове, что и обеспечило обнаружение факта ошибки и ее места в словах, чтобы внести исправление. А (7, 4)-код получил новое прилагательное и стал линейным блоковым двоичным.

Линейные функциональные зависимости (правила (*)) вычислений значений символов

имеют следующий вид:

Исправление ошибки стало очень простой операцией — в ошибочном разряде определялся символ (ноль или единица) и заменялся другим противоположным 0 на 1 или 1 на 0.
Сколько же различных слов образуют код? Ответ на этот вопрос для (7, 4)-кода получается очень просто. Раз имеется лишь 4 информационных разряда, а их разнообразие при заполнении символами имеет

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

Информационные части этих 16 слов получают нумерованный вид №
(

):

0=0000; 4= 0100; 8=1000; 12=1100;
1=0001; 5= 0101; 9=1001; 13=1101;
2=0010; 6= 0110; 10=1010; 14=1110;
3=0011; 7= 0111; 11=1011; 15=1111.

Каждому из этих 4-разрядных слов необходимо вычислить и добавить справа по 3 проверочных разряда, которые вычисляются по правилам (*). Например, для информационного слова №6 равного 0110 имеем

и вычисления проверочных символов дают для этого слова такой результат:

Шестое кодовое слово при этом приобретает вид:

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

Таблица К – кодовые слова Сj, j = 0(1)15, (7, 4) – кода Хемминга

Описание таблицы: 16 строк — кодовые слова; 10 колонок: порядковый номер, десятичное представление кодового слова, 4 информационных символа, 3 проверочных символа, W-вес кодового слова равен числу ненулевых разрядов (≠ 0). Заливкой выделены 4 кодовых слова-строки — это базис векторного подпространства. Собственно, на этом все — код построен.

Таким образом, в таблице получены все слова (7, 4) — кода Хемминга. Как видите это было не очень сложно. Далее речь пойдет о том, какие идеи привели Хемминга к такому построению кода. Мы все знакомы с кодом Морзе, с флотским семафорным алфавитом и др. системами построенными на разных эвристических принципах, но здесь в (7, 4)-коде используются впервые строгие математические принципы и методы. Рассказ будет как раз о них.

Математические основы кода. Высшая алгебра

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

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

Создатели кодов, долго не могли додуматься до кода, обнаруживающего и исправляющего две ошибки. Идеи, использованные Хеммингом, там не срабатывали. Пришлось искать, и нашлись новые идеи. Очень интересно! Захватывает. Для поиска новых идей потребовалось около 10 лет и только после этого произошел прорыв. Коды, обнаруживающие произвольное число ошибок, были получены сравнительно быстро.

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

Из 128 слов в код включены лишь 16, но они попали в состав кода не просто так.

Во-первых, они являются подпространством со всеми вытекающими отсюда свойствами и особенностями, во-вторых, кодовые слова являются подгруппой большой группы порядка 128, даже более того, аддитивной подгруппой конечного расширенного поля Галуа GF(

) степени расширения n = 7 и характеристики 2. Эта большая подгруппа раскладывается в смежные классы по меньшей подгруппе, что хорошо иллюстрируется следующей таблицей Г. Таблица разделена на две части: верхняя и нижняя, но читать следует как одну длинную. Каждый смежный класс (строка таблицы) — элемент факторгруппы по эквивалентности составляющих.

Таблица Г – Разложение аддитивной группы поля Галуа GF () в смежные классы (строки таблицы Г) по подгруппе 16 порядка.

Столбцы таблицы – это сферы радиуса 1. Левый столбец (повторяется) – синдром слова (7, 4)-кода Хемминга, следующий столбец — лидеры смежного класса. Раскроем двоичное представление одного из элементов (25-го выделен заливкой) факторгруппы и его десятичное представление:

Техника получение строк таблицы Г. Элемент из столбца лидеров класса суммируется с каждым элементом из заголовка столбца таблицы Г (суммирование выполняется для строки лидера в двоичном виде по mod2). Поскольку все лидеры классов имеют вес W=1, то все суммы отличаются от слова в заголовке столбца только в одной позиции (одной и той же для всей строки, но разных для столбца). Таблица Г имеет замечательную геометрическую интерпретацию. Все 16 кодовых слов представляются центрами сфер в 7-мерном векторном пространстве. Все слова в столбце от верхнего слова отличаются в одной позиции, т. е. лежат на поверхности сферы с радиусом r =1.

В этой интерпретации скрывается идея обнаружения одной ошибки в любом кодовом слове. Работа идет со сферами. Первое условие обнаружения ошибки — сферы радиуса 1 не должны касаться или пересекаться. Это означает, что центры сфер удалены друг от друга на расстояние 3 или более. При этом сферы не только не пересекаются, но и не касаются одна другой. Это требование для однозначности решения: какой сфере отнести полученное на приемной стороне декодером ошибочное (не кодовое одно из 128 -16 = 112) слово.

Второе — все множество 7-разрядных двоичных слов из 128 слов равномерно распределено по 16 сферам. Декодер может получить слово лишь из этого множества 128-ми известных слов с ошибкой или без нее. Третье — приемная сторона может получить слово без ошибки или с искажением, но всегда принадлежащее одной из 16-и сфер, которая легко определяется декодером. В последней ситуации принимается решение о том, что послано было кодовое слово — центр определенной декодером сферы, который нашел позицию (пересечение строки и столбца) слова в таблице Г, т. е номера столбца и строки.

Здесь возникает требование к словам кода и к коду в целом: расстояние между любыми двумя кодовыми словами должно быть не менее трех, т. е. разность для пары кодовых слов, например, Сi = 85=

=1010101; Сj = 25=

= 0011001 должна быть не менее 3; 85 — 25 = 1010101 — 0011001 =1001100 = 76, вес слова-разности W(76) = 3. (табл. Д заменяет вычисления разностей и сумм). Здесь под расстоянием между двоичными словами-векторами понимается количество не совпадающих позиций в двух словах. Это расстояние Хемминга, которое стало повсеместно использоваться в теории, и на практике, так как удовлетворяет всем аксиомам расстояния.

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

Таблица Д — Сумма элементов группы (кодовых слов), используемой для построения кода Хемминга

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

Применение кода. Кодер

Кодер размещается на передающей стороне канала и им пользуется отправитель сообщения. Отправитель сообщения (автор) формирует сообщение в алфавите естественного языка и представляет его в цифровом виде. (Имя символа в ASCII-соде и в двоичном виде).
Тексты удобно формировать в файлах для ПК с использованием стандартной клавиатуры (ASCII — кодов). Каждому символу (букве алфавита) соответствует в этой кодировке октет бит (восемь разрядов). Для (7, 4)- кода Хемминга, в словах которого только 4 информационных символа, при кодировании символа клавиатуры на букву требуется два кодовых слова, т.е. октет буквы разбивается на два информационных слова естественного языка (ЕЯ) вида

.

Пример 1. Необходимо передать слово «цифра» в ЕЯ. Входим в таблицу ASCII-кодов, буквам соответствуют: ц –11110110, и –11101000, ф – 11110100, р – 11110000, а – 11100000 октеты. Или иначе в ASCII — кодах слово «цифра» = 1111 0110 1110 1000 1111 0100 1111 0000 1110 0000

с разбивкой на тетрады (по 4 разряда). Таким образом, кодирование слова «цифра» ЕЯ требует 10 кодовых слов (7, 4)-кода Хемминга. Тетрады представляют информационные разряды слов сообщения. Эти информационные слова (тетрады) преобразуются в слова кода (по 7 разрядов) перед отправкой в канал сети связи. Выполняется это путем векторно-матричного умножения: информационного слова на порождающую матрицу. Плата за удобства получается весьма дорого и длинно, но все работает автоматически и главное — сообщение защищается от ошибок.
Порождающая матрица (7, 4)-кода Хемминга или генератор слов кода получается выписыванием базисных векторов кода и объединением их в матрицу. Это следует из теоремы линейной алгебры: любой вектор пространства (подпространства) является линейной комбинацией базисных векторов, т.е. линейно независимых в этом пространстве. Это как раз и требуется — порождать любые векторы (7-разрядные кодовые слова) из информационных 4-разрядных.

Порождающая матрица (7, 4, 3)-кода Хемминга или генератор слов кода имеет вид:

Справа указаны десятичные представления кодовых слов Базиса подпространства и их порядковые номера в таблице К
№ i строки матрицы — это слова кода, являющиеся базисом векторного подпространства.

Пример кодирования слов информационных сообщений (порождающая матрица кода выстраивается из базисных векторов и соответствует части таблицы К). В таблице ASCII-кода берем букву ц = <1111 0110>.

Информационные слова сообщения имеют вид:

.

Это половины символа (ц). Для (7, 4)-кода, определенного ранее, требуется найти кодовые слова, соответствующее информационному слову-сообщению (ц) из 8-и символов в виде:

.

Чтобы превратить эту букву–сообщение (ц) в кодовые слова u, каждую половинку буквы-сообщения i умножают на порождающую матрицу G[k, n] кода (матрица для таблицы К):

Получили два кодовых слова с порядковыми номерами 15 и 6.

Покажем детальное формирование нижнего результата №6 – кодового слова (умножение строки информационного слова на столбцы порождающей матрицы); суммирование по (mod2)

<0110> ∙ <1000> = 0∙1 +1∙0 + 1∙0 + 0∙0 = 0(mod2);
<0110> ∙ <0100> = 0∙0 +1∙1 + 1∙0 + 0∙0 = 1(mod2);
<0110> ∙ <0010> = 0∙0 +1∙0 + 1∙1 + 0∙0 = 1(mod2);
<0110> ∙ <0001> = 0∙0 +1∙0 + 1∙0 + 0∙1 = 0(mod2);
<0110> ∙ <0111> = 0∙0 +1∙1 + 1∙1 + 0∙1 = 0(mod2);
<0110> ∙ <1011> = 0∙1 +1∙0 + 1∙1 + 0∙1 = 1(mod2);
<0110> ∙ <1101> = 0∙1 +1∙1 + 1∙0 + 0∙1 = 1(mod2).

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

, (в таблице ASCII это только половины буквы ц). Для кодирующей матрицы выбраны в качестве базисных векторов в таблице К совокупности слов с номерами: 1, 2, 4, 8. В таблице они выделены заливкой. Тогда для этой таблицы К кодирующая матрица получит вид G[k,n].

В результате перемножения получили 15 и 6 слова таблицы К кода.

Применение кода. Декодер

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

Основной задачей декодера является проверка того, является ли полученное слово (7 разрядов) тем, которое было отправлено на передающей стороне, не содержит ли слово ошибок. Для решения этой задачи для каждого полученного слова декодером путем умножения его на проверочную матрицу Н[n-k, n] вычисляется короткий вектор-синдром S (3 разряда).

Для слов, которые являются кодовыми, т. е. не содержат ошибок, синдром всегда принимает нулевое значение S =<000>. Для слова с ошибкой синдром не нулевой S ≠ 0. Значение синдрома позволяет обнаружить и локализовать положение ошибки с точностью до разряда в принятом на приемной стороне слове, и декодер может изменить значение этого разряда. В проверочной матрице кода декодер находит столбец, совпадающий со значением синдрома, и порядковый номер этого столбца принимает равным искаженному ошибкой разряду. После этого для двоичных кодов декодером выполняется изменение этого разряда – просто замена на противоположное значение, т. е. единицу заменяют нулем, а нуль – единицей.

Рассматриваемый код является систематическим, т. е. символы информационного слова размещаются подряд в старших разрядах кодового слова. Восстановление информационных слов выполняется простым отбрасыванием младших (проверочных) разрядов, число которых известно. Далее используется таблица ASCII-кодов в обратном порядке: входом являются информационные двоичные последовательности, а выходом – буквы алфавита естественного языка. Итак, (7, 4)-код систематический, групповой, линейный, блочный, двоичный.

Основу декодера образует проверочная матрица Н[n-k, n], которая содержит число строк, равное числу проверочных символов, а столбцами все возможные, кроме нулевого, столбцы из трех символов

. Проверочная матрица строится из слов таблицы К, они выбираются так, чтобы быть ортогональными к кодирующей матрице, т.е. их произведение — нулевая матрица. Проверочная матрица получает следующий вид в операциях умножения она транспонируется. Для конкретного примера проверочная матрица Н[n-k, n] приведена ниже:

Видим, что произведение порождающей матрицы на проверочную в результате дает нулевую матрицу.

Пример 2. Декодирование слова кода Хемминга без ошибки (е<7> =<0000000>).
Пусть на приемном конце канала приняты слова №7→60 и №13→105 из таблицы К,
u<7> + е<7> = <0 1 1 1 1 0 0 > + <0 0 0 0 0 0 0>,
где ошибка отсутствует, т. е. имеет вид е<7> = <0 0 0 0 0 0 0>.

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

Пример 3. Обнаружение одной ошибки в слове, полученном на приемном конце канала (таблица К).

А) Пусть требуется передать 7 – е кодовое слово, т.е.

u<7> = <0 1 1 1 1 0 0> и в одном третьем слева разряде слова, допущена ошибка. Тогда она суммируется по mod2 с 7-м передаваемым по каналу связи кодовым словом
u<7> + е<7> = <0 1 1 1 1 0 0 > + <0 0 1 0 0 0 0> = <0 1 0 1 1 0 0>,
где ошибка имеет вид е<7> = <0 0 1 0 0 0 0>.

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

Выполним такое умножение для наших исходных (7-го вектора с ошибкой) данных.

В результате такого умножения на приемном конце канала получили вектор-синдром S<n-k>, размерность которого (n–k). Если синдром S<3>= <0,0,0> нулевой, то делается вывод о том, что принятое на приемной стороне слово принадлежит коду С и передано без искажений. Если синдром не равен нулю S<3> ≠ <0,0,0>, то его значение указывает на наличие ошибки и ее место в слове. Искаженный разряд соответствует номеру позиции столбца матрицы Н[n-k, n], совпадающего с синдромом. После этого искаженный разряд исправляется, и полученное слово обрабатывается декодером далее. На практике для каждого принятого слова сразу вычисляется синдром и при наличии ошибки, она автоматически устраняется.

Итак, при вычислениях получен синдром S=<110> для обоих слов одинаковый. Смотрим на проверочную матрицу и отыскиваем в ней столбец, совпадающий с синдромом. Это третий слева столбец. Следовательно, ошибка допущена в третьем слева разряде, что совпадает с условиями примера. Этот третий разряд изменяется на противоположное значение и мы вернули принятые декодером слова к виду кодовых. Ошибка обнаружена и исправлена.

Вот собственно и все, именно так устроен и работает классический (7, 4)-код Хемминга.

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

Заключение

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

Задача защиты информационного взаимодействия субъектов и объектов от ошибок среды и от воздействий нарушителя относится к кодологии.

Рассмотрен в деталях (7, 4)-код Хемминга, положивший начало нового направлению в теории кодирования — синтеза корректирующих кодов.

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

Литература

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976, 594 c.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер.с англ. М.: Мир, 1986, 576 с.

Изобретение относится к вычислительной технике, в частности к устройствам обнаружения и исправления ошибок, возникающих при хранении или передаче цифровой информации. Целью изобретения является повышение быстродействия устройства . Указанная цель достигается путем устранения избыточной коррекции, контрольных символов за счет введения в корректор блока селекции ошибок контрольных символов с информацией, указывающей, в каком месте кодового слова — в поле информационных или в поле контрольных символов произошла ошибка. Корректор ошибок содержит синдромный регистр, блок обратной связи, детектор ошибки, блок фиксации местоположения ошибки, буфер данных, блок коррекции ошибки, блок управления и блок селекции ошибок контрольных символов . 2 ил. С/)

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 11 С 29/00

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛ ЬСТВУ (21) 4761070/24 (22) 21,11.89 (46) 23.04.93. Бюл. N 15 (71) Институт кибернетики им, В.М.Глушкова (72) В.В.Звягинцев (56) Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. — M.: Радио и связь, 1987, с. 71-85, Блейхут P. Теория и практика кодов, контролирующих ошибки, — M.: Мир, 1986, с, 174. (54) КОРРЕКТОР ОШИБОК (57) Изобретение относится к вычислительной технике, в частности к устройствам обнаружения и исправления ошибок, возникающих при хранении или передаче

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

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

СО мационного слова по определенному алго-: ритму формируются. контрольные символы

Укон р. После присоединения контрольных символов к информационному слову получа-: ется кодовое слово чк0д циклического блокового систематического (n, k) — кода; где п — Р общее количество символов в кодовом слове, k — количество информационных симво-; ° лов: m = n — k — количество контрольных символов. При этом часто пользуются пол- иноминальным представлением кодовых векторов, что позволяет задавать циклический код математически с помощью так называемых порождающих многочленов. Например, порождающий многочлен У=х +х+1 над полем символов алфавита GF2 задает(31, 26) — код Хэмминга, исправляющий одну случайную ошибку.

1810909

Формирование контрольных символов в процессе кодирования осуществляется путем вычисления остаточного многочлена чконтр = чинф. х modY с испол ьзованием арифметики полей Галуа. При приеме сообщения осуществляют его декодирование с целью обнаружения и исправления ошибок, возникающих при хранении или передаче, Принятое слово может быть представлено в . виде суммы передаваемого кодового слова чк д и вектора ошибки vp . Вычисление при декодировании остаточного многочлена нконтр = (чкод+ чош) х mod Y позволЯет пол учить контрольные символы вектора ошибки, называемые синдромом. Располагая известным значением синдрома, можно, используя специальные устройства, называемые декодерами или корректорами ошибок, сформировать вектор ошибки и воссоздать в первоначальном виде переданное кодовое слово.

Известно устройство для коррекции независимых ошибок (см.Питерсон У., Уэлдон

Э. Коды. исправляющие ошибки, — М,: Мир, 1976, с. 191). Для этого корректора характерно недостаточное быстродействие, что обусловлено потерями времени на коррекцию кодовых слов, у которых искажены контрольные символы, Этот же недостаток присущ и корректору пачек ошибок (см.Портной С.А., Анкудинов Д.P. Кодеки корректирующих блочных кодов, — Зарубежная радиоэлектроника, 1985, N. 7, с. 3 — 27).

Известен корректор ошибок с неалгебраическим последовательным декодированием символов циклического систематического кода, в частности кода

Хэмминга (см,Блейхут P., Теория и практика кодов, контролирующих ошибки. — М,; Мир, 1986, стр. 174). Это устройство выбрано в качестве прототипа.

Схема прототипа приведена на фиг. 1.

Она содержит синдромный регистр 1, блок обратной связи 2, детектор ошибки 3. блок фиксации местоположения ошибки 4, буфер данных 5, блок коррекции ошибки 6 и блок управления 7; выход блока обратной связи

2 соединен с информационным входом синдромного регистра 1, выходы которого соединены с соответствующими информационными входами детектора ошибки 3 и блока фиксации местоположения ошибки 4, выход которого соединен со входами коррекции блока обратной связи 2 и блока коррекции ошибки 6, выход которого подключен к выходу 17 устройства и является информационным выходом корректора ошибок, выход детектора ошибки 3 подключен к выходу 16 устройства и является управляющим выходом корректора ошибок, информационные входы блока обратной связи 2; буфера данных 5 и первый информационный вход блока коррекции ошибки 6 объединены и подключены к входу

8 устройства, являющемуся информационным входом корректора ошибок, управляющие входы блока фиксации местоположения ошибки 4, детектора ошибки 3, блока коррекции ошибки 6 и блока обратной связи 2 подключены к управляющему выходу регистра синдрома 1, входы сброса и сдвига которого соединены соответственно с первым и вторым выходами блока управления 7, третий выход которого соединен с входом разрешения работы блока фиксации местоположения ошибки 4, второй информационный вход блока коррекции ошибки 6 соединен с выходом буфера данных 5, адресные входы и входы чтения, записи, обращения которого соединены соответственно с четвертым, пятым, шестым и седьмым выходами блока управления 7, восьмой, девятый и десятый выходы которого подключены к выходам 14, 15, 13 устройства и являются соответственно выходом синхронизации источника информации, выходом синхронизации приемника информации и выходом готовности корректора ошибок, входы начальной установки, сброса ошибки, чтения и коррекции блока управления 7 подключены к входам 9, 10, 11, 12 устройства и являются соответственно входом начальной установки, входом сброса ошибки, входом чтения и входом коррекции корректора ошибок.

Синдромный регистр 1 при приеме сообщений обеспечивает формирование контрольных символов (синдрома) кодового слова, поступающего с входа 8 устройства на информационный вход блока 2 обратной связи и с выхода последнего — на информационный вход регистра 1. Формирование синдрома осуществляется посредством посимвольного деления кодового слова qa по,рождающий многочлен. Прием и деление кодового слова на порождающий многочлен начинается с его,старших символов, Остатки от деления отдельных символов накапливаются в синдромном регистре 1, Окончательный результат получается после приема последнего (младшего) символа кодового слова. При обнаружении ошибки и принятом сообщении (синдром не равен нулю) регистр 1 и содержащийся в нем синдром используются для построения вектора

1810909 ошибки. Это осуществляется посредством модульного умножения синдрома. что обес печивается сдвигом вправо регистра синдрома 1. Сдвиг и сброс синдромного регистра

1 производится сигналами из блока управления 7, поступающими на входы сдвига и сброса регистра 1.

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

2 разрешает или запрещает прохождение сигналов обратной связи на информационный вход регистра 1.

Детектор ошибки 3 вырабатывает сигнал «1», если содержимое синдромного регистра 1 не равно О. В режиме чтения это свидетельствует. о присутствии обнаруживаемых ошибок, а в режиме коррекции— неисправимых ошибок в принятом сообщении. Блок фиксации местоположения ошибки 4 в режиме коррекции вырабатывает выходной сигнал в момент завершения формирования синдромным регистром 1 вектора ошибки. Сигнал коррекции с выхода блока 4 поступает в блоки 6 и 2 для коррекции обнаруженной ошибки и соответствующего ей синдрома.

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

В блоке коррекции ошибки 6 происходит непосредственное исправление ошибок принятого кодового слова путем его посимвольного сложения (в случае двоичных кодов — по модулю два) с вектором ошибки, Блок управления 7 обеспечивает взаимодействие и синхронизацию работы узлов устройства. Блок 7 формирует сигналы сброса и сдвига синдромного регистра 1, сигнал управления блоком фиксации местоположения ошибки 4, сигналы записи. чтения, обращения, а также адресные сигналы буфера данных 5; сигналы готовности устройства, синхронизации источника и приемника информации.

Устройство-прототип работает следующим образом. Перед чтением в блок управления 7-от приемника информации через входы 9″ и 10 корректора ошибок поступают сигналы начальной установки устройства и сброса ошибки, осуществляющее сброс синдромного регистра 1 и подготовку к работе блока управления. Затем на вход 11 устройства приемник информации подает сигнал чтения и блок управления сбрасывает сигнал готовности на выходе 13 устройства и формирует последовательность сигналов синхронизации, которые с выхода

14 поступают к источнику кодированных со»0 общений. 3а одну команду чтения обеспечивается прием одного кодового слова. В ответ на каждый синхросигнэл источник сообщений передает один символ, Эти симво.лы ccr âxoäà 8 корректора ошибок без изменений через блок коррекции ошибок 6 поступают на информационный выход 17 и далее — к приемнику информации в сопровождении сигналов синхронизации на выхо20 де 15 устройства, Одновременно принимаемые символы записываются в буфер данных 5 и поступают в блок обратной связи 2 для деления на порождающий многочлен, После приема очередного символа блок управления 7 сдвигает вправо на.один разряд синдромный регистр 1 и инкрементирует на 1 код адреса на адресных входах буфера данных 5. Таким образом s процессе последовательного посимвольного деления принятого кодового слова в регистре 1 накапливаются частичные остатки от деления всех символов кодового слова, образую щие в конечном итоге умножений на х синдром ошибки S = (шкод+ ош) х п обУ.

35 После приема всех и символов кодового слова блок управления 7 останавливается и выдает на выход 13 устройства сигнал готовности. Если содержимое синдромного регистра 1 в этот момент не будет равно О, 40 то детектор ошибки 3 сформирует сигнал ошибки, который поступит на выход 16 устройства. Восприняв сигнал готовности корректора ошибок, приемник информации анализирует значение сигнала ошибки на выходе 16 корректора ошибок, Если сигнал ошибки отсутствует, то чтение кодового слова закончено. и приемник информации выдает вышеописанную последовательность команд для чтения следующего кодового слова, При наличии сигнала ошибки работа . устройства по декодированию принятого кодового слова должна быть продолжена с целью осуществления коррекции ошибоч55 ных символов. Для этого от приемника информации на входы 9 и 12 устройства подаются сигналы начальной установки и коррекции. Блок управления 7 при этом разрешает работу блока фиксации местоположения ошибки 4, переводит буфер данных 5

s режим чтения и сбрасывает сигнал готовности. Затем блок управления 7 формирует сигналы обращения к буферу данных 5, сдвига синдромного регистра 1, инкрементирования кода адреса на адресных входах буфера данных. Считываемое из буфера данных 5 искаженное кодовое слово посимвольно поступает в блок коррекции ошибки

6 и при отсутствии сигнала на выходе блока фиксации местополо>кения ошибки 4 без изменений передается через блок 6 на выход

17 устройства. Выдаваемые сигналы сопровождаются сигналами синхронизации на выходе 15 устройства. Одновременно с выдачей очередного символа сдвигается на один разряд вправо синдромный регистр 1 для умножения на х содер>кащегося в нем синдрома, После того, как в процессе последовательного умножения синдрома в регистре 1 будет сформирован вектор ошибки, блок 4 вырабатывает выходной сигнал, который поступит на вход коррекции блока 2 и разорвет обратную связь синдромного регистра 1, обеспечивая тем самым сохранность остающихся в нем при последующих сдвигах символов вектора ошибки. Этот же сигнал поступит на вход коррекции блока 6 и разрешит передачу вектора ошибки с управляющего выхода синдромного регистра

1 в блок 6. В блоке 6 происходит сложение искаженных символов кодового, слова, поступающих из буфера данных 5..-с символами вектора ошибки. Исправленные таким образом символы кодового слова с выхода

17 и сопровождающие их сигналы синхронизации с выхода 15 корректора ошибок поступают в приемник информации. После окончания передачи исправленного сообщения блок управления 7 останавливается и выдает на выход 13 устройства сигнал готовности. Если процесс исправления ошибок прошел успешно, то на выходе 16 устройства в этот момент будет отсутствовать сигнал ошибки. В противном случае, а это бывает при обнаружении неисправимых ошибок. на выходе 16 устройства будет присутствовать сигнал ошибки, и уже дело приемника информации решать, что делать в этом случае — оперировать и искаженной информацией, осуществить повторное чтение кодового слова или вообще прекратить дальнейшую рабату.

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

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

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

Предлагаемое устройство изображено

35 на фиг. 2, Оно .содержит синдромный регйстр 1, включающий одноразрядные сдвигающие регистры 2, связанные через схемы.

3 сложения по модулю два, и ключи 4 задания коэффициентов порождающего много40 члена, блок обратной связи 5, детектор ошибки 9, блок фиксации местоположения ошибки 10, буфер данных 11, блок коррекции ошибки 12, блок селекции ошибок контрольных символов 16 и блок управления 17;

45 выход блока обратной связи 5 соединен с информационным входом синромного регистра 1, выходы которого соединены с соответствующими информационными входами детектора ошибки 9, блока селекции ошибок контрольных символов 16 и блока фиксации местоположения ошибки 10, выход которого соединен со входом коррекции блока обратной связи 5 и блока коррекции ошибки 12, 55 выход которого подключен к выходу 27 устройства и является информационным выходом корректора ошибок, выход детектора ошибки 9 соединен с выходом 26 устройства и является первым управляющим выходом корректора ошибок, информационные вхо1810909

10 ды блока обратной связи 5. буфера данных

11 и первый информационной вход блока коррекции ошибки 12 обьединены и подключены к входу 18 устройства, являющемуся информационным входом корректора ошибок, управляющие входы блока фиксации местоположения ошибки 10, детектора ошибки 9, блока коррекции ошибки 12 и блока обратной связи 5 подключены к управляющему выходу регистра синдрома 1, входы сброса и сдвига которого соединены соответственно с первым и вторым выходами блока управления 17, третий выход которого соединен с входом разрешения работы блока фиксации местоположения ошибки

10, второй информационный вход блока коррекции ошибки 12 соединен с выходом буфера данных 11. адресные входы и входы чтения, записи, обращения которого соединены соответственно с четвертым, пятым, шестым и седьмым выходами блока управления 17, восьмой, девятый и десятый выходы которого подключены к выходам 24, 25, 23 устройства и являются соответственно выходом синхронизации источника информации, выходом синхронизации приемника информации и выходом готовности корректора ошибок, входы начальной установки, . сброса ошибки, чтения и коррекции блока управления 17 подключены к входам 19, 20, 21, 22 устройства и являются соответственно входом начальной установки, входоM сброса ошибки, входом чтения и входом коррекции корректора ошибок, одиннадцатый выход блока управления 17 соединен с управляющим входом блока селекции ошибок контрольных символов 16, выход которого подключен к выходу 28 устройства и является вторым управляющим выходом корректора ошибок.

Сдвигающие регистры 2, схемы 3 сложения по модулю два и ключи 4 задания коэффициентов многочлена, порождающего циклический код, образуют синдромный регистр 1. Этот регистр при приеме сообщений обеспечивает формирование контрольных символов (синдрома) кодового слова, поступающего с выхода блока 5 на информационный вход регистра 1. Формирование синдрома осуществляется путем посимвольного деления на порождающий многочлен кодового слова, начиная с его старших символов, Остатки от деления отдельных символов накапливаются в синдромном регистре 1. Окончательный результат получается после приема последнего (младшего) символа кодового слова. При обнаружении ошибки в принятом сообщении (синдром не равен нулю) регистр 1 и содержащийся в нем синдром используются для построения вектора ошибки, которое осуществляется посредством модульного умножения синдрома при сдвигах вправо регистра синдрома 1. Сдвиг и сброс регистра 1 производится сигналами, поступающими из блока управления 17, В случае двоичных циклических кодов для полиномиального представления порождающего многочлена и кодового слова в виде

O х используется алфавит из двух

i=O символов — «0» и «1». Соответственно коэффициенты ai многочлена также могут. принимать только два указанных значения.

Например, синдромный регистр для декодирования циклического кода, заданного порождающим многочленом Y = х + х 1 =

5, 15

i а х, а =- а1 = а5 = 1, 82= аз = а4 = О, i =0 ных информационных сигналов для синдромного регистра 1, используя для этого входные информационные сигналы корректора ошибок, поступающие. на вход 18 от источника сообщений, а также сигналы обсодержит 5 одноразрядных сдвигаюьцих регистров, причем в замкнутом положении находятся только два крайних слева ключа, 30 задающих коэффициенты а и а>. Если коэффициенты Bl постоянны, то ключи 4 могут быть фиксированными (запаянными) связями. Выходами синдромного регистра 1 являются выходы входящих в его состав сдвигающих регистров 2. Сигнал с выхода старшего — крайнего справа разряда (управляющий выход) через блок 5 участвует в выработке . сигналов обратной связи синдромного регистра 1, Блок 5 обратной связи содержит двухвходовую схему И7, инвертор 6 и двухвходовую схему сложения по модулю два 8, Блок имеет 3 входа и 1 выход. Вход инвертора 6 является входом коррекции блока 5, Один из

45 входов схемы И7 соединен с управляющим выходом синдромного регистра 1 и является управляющим входом блока 5. Информационным входом блока 5 является вход схемы

8 сложения по модулю два, соединенный с

50 информационным входом l8 устройства, Выход схемы 8 сложения по модулю два— он же выход блока 5 соединен с информационным входом синдромного регистра 1.

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

Детектор ошибки 9 представляет собой схему И вЂ” НЕ числом входов, равным количеству разрядов синдромного регистра 1.

При наличии ошибок в принятом кодовом слое содержимое регистра синдрома 1 не будет равно 0 и детектор ошибки сформирует «1» на своем выходе, который является первым управляющим выходом устройства.

В противном случае содержимое регистра синдрома 1 и выходной сигнал детектора ошибки будут равны О.

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

Этот сигнал поступает в блоки 5, 12 для коррекции обнаруженной ошибки и соответствующего ей синдрома.

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

Адресные сигналы, сигналы чтения, записи и обращения к буферу данных формируются в блоке управления 17, В блоке коррекции ошибки 12 проихсодит непосредственное исправление ошибок принятого кодового слова путем его посимвольного сложения (в случае двоичных кодов — по модулю два) с веткаром ошибки. Блок 12 содержит двухходовую схему И 13, двухвходовую схему сложения по модулю два 14 и двухвходовую схему ИЛИ 15, Первый вход схемы И 13 соединен с выходом блока 10 и является одновременно входом коррекции блока 12. Второй вход схемы И13, связанный с управляющим выходом синдромного регистра 1, является управляющим входом блока

12, Первым информационным входом блока

12 является вход схемы ИЛИ 15. соединенный с информационным входом 18 корректора ошибок. Второй информационный вход блока 12 образует вход схемы сложения по модулю два 14, соединенный с выходом буфера данных 11, Выход схемы ИЛИ

15 является одновременно выходом блока

12, Блок селекции ошибок контрольных символов 16, являющийся отличительным признаком предлагаемого устройства, предназначен для выделения ошибок контрольных символов из всей совокупности ошибок кодового слова. Информационные входы блока 16 соединены с выходами регистра синдрома 1, а управляющий вход, разрешающий работу блока 16 в режиме чтения, — с выходом блока управления 17.

Выход блока 16 является одновременно вторым, управляющим выходом устройства.

Сигнал «1» на .этом выходе формируется, если в принятом кодовом слове ошибочными являются контрольные символы; в про25 тивном случае формируется сигнал «0».

Блок селекции ошибок контрольных символов может быть реализован на комбинационных логических схемах, на базе арифметико-логического устройства или

30 ПЗУ. Ниже рассмотрен пример реализации блока 16 на основе ПЗУ. Для представления информации об ошибках контрольных символов в ПЗУ достаточно одного бита на ошибку: «1» может быть использована для

35 кодирования ошибок контрольных символов, а «0» — для кодирования всех других ошибок. В случае например (31, 26) — кода

Хэмминга с пооождающим многочленом

Y = х +х+1 из 2 = 32 возможных значений

40 синдрома только пять следующих: x+1, х + . х +х, х +х, х +х+1 будут являться синдро3 4 3 мами ошибок контоольных символов, умно женными на х . Им соответствуют

5-разрядные адреса ПЗУ: 00011, 00110, 01100, 11000, 10011. По этим адресам в ПЗУ надо записать «1», а по остальным — «0».

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

Если при чтении будет получена «1», то ошибка принадлежит к-контрольным символам. Чтение информации из ПЗУ инициируется сигналом блока управления, поступающим на управляющий вход (вход разрешения обращения) ПЗУ, Выпускаемые в настоящее время БИС

ПЗУ, в частности серии 556 емкостью 1К—

64 К бит в одном корпусе, позволяют созда13 1810909 вать корректоры ошибок, оперирующие с кодовыми словами любой длины.

Блок управления 17 обеспечивает взаимодействие и синхронизацию работы узлов устройства. Схема блока управления приведена на фиг. 3, Она включает RS-триггеры

12, 13, 29; генератор тактовых импульсов 15; схемы ИЛ И 16, 24. 41, 42; схемы И 17, 23, 31, 32, 37, 38; инверторы l8, 33, 35; D-триггеры

26,28: схему ИЛИ-Н Е 27, схемы задержки 39, 40; счетчик тактовых импульсов 44, усилители 14, 25, 30, 34, 36, 43; вход усилителя 14

10 соединен с входом 19 начальной установки устройства, а выход — со входами сброса триггеров 12, 13, 26, 28, счетчика тактовых импульсов 44, а также с первым входом схемы ИЛИ 24; вход усилителя 25 соединен с входом 20 сброса ошибки устройства, а выход — с выходом 1 блока управления. Входы установки в «1» триггеров 12, 13 соединены соответственно со входами 21, 22 чтения и коррекции устройства, выход триггера 12 соединен с первыми входами схемы ИЛИ 16 и схем И 23, 38, а также с выходом 6 блока управления; выход триггера 13 соединен со вторым входом схемы ИЛИ 16 и с первыми входами схем И 17, 37, а также через усилители 30,36 — с выходами 5, 3 блока управления, выход генератора тактовых импульсов 15 соединен с тактовым входом D-триггера 26 и с первыми входами схем И 31, 32, информационный вход Dтриггера 26 соединен с выходом схемы ИЛИ

16, а выход — с вторым входом схемы И 31, третий вход которой соединен с выходом схемы ИЛИ вЂ” НЕ 27, выход схемы И 17 соединен с входом инвертора 18 и с первым входом схемы ИЛИ-НЕ 27, выход схемы И

23 соединен с информационным входом Dтриггера 28, и с вторыми входами схемы

ИЛИ вЂ” НЕ 27 и схемы И 32, третий вход которой соединен с выходом 0-триггера 28, а выход — с тактовыми входом D-триггера 28, 4 входом инвертора 33 и с выходом

11 блока управления. выход схемы

И 31 соединен со вторыми входами схем И 37, 38 и с входом инвертора 35; второй и третий входы схемы ИЛИ 24 соединены с выходами инверторов 18, 33; входы сброса и установки триггера 29 соединены с выходами схемы ИЛИ 24 и инвертора 35, а выход — через усилитель 34 подключен к выхоДу 10 блока управления и к выходу готовности 23 устройства. Выход схемы И 37 соединен с первым входом схемы ИЛИ 41 и через схему задержки 40- с первым входом схемы ИЛИ 42; выход схемы И 38 соединен с выходом 8 блока управления и с выходом

24 синхронизации источника информации устройства. а также через схему задержки

39 — со вторым входами схем ИЛИ 41, 42; выход схемы ИЛИ 41 соединен со счетным входом счетчика 44, и с выходом 7 блока управления; выход схемы ИЛИ 42 подключен к выходу 2 блока. управления. а также через усилитель 43; к выходу 9 блока управления и к выходу 25 синхронизации приемника информации устройства, информационные входы счетчика 44 соединены со вторыми входами схем И 17, 23 и с выходом 4 блока управления.

Блок управления работает следующим образом. Сигналами, поступающими от приемника информации на входы 19> 20, производится сброс синдромного регистра 1 устройства, а также триггеров 12, 13, 26, 28, 29 и счетчика 44 блока управления. В результате этого на выход 10 с выхода триггера 29 через усилитель 34 будет выдаваться сигнал готовности устройства к работе, а на выход 4 — начальный (нулевой) адрес буфера данных 11; на всех других выходах блока управления сигналы будут отсутствовать. В режиме чтения сигнал от приемника информации со входа 21 устанавливает в «1» триггер 12, выходной сигнал которого с выхода

6 переводит буфер данных 11 устройства в режим записи и через схему ИЛИ 16 поступает на информационный вход D-триггера

26, Отрицательный задний фронт первого положительного тактового импульса генератора 15, накладывающийся на выходной сигнал схемы ИЛИ 16, воздействуя на тактовый вход D-триггера 26, устанавливает его в «1» и разрешает прохождение всех последующих положительных тактовых импульсов генератора 15 через вентиль 31 на входы вентилей 37, 38 и инвертора 35. Первый выходной сигнал инвертора 35 устанавливает в «1» триггер 29, в результате на выходе

10 блока управления и на выходе 23 устройства снимается сигнал готовности, Проходя через открытый выходным сигналом триггера 12 вентиль 38, тактовые импульсы поступают на выход 8 синхронизации источника информации и через схему задержки 39, схемы ИЛИ 41, 42 — на выходы 7, 2, 9 разрешения обращения к буферу данных, сдвига синдромного регистра и синхронизации приемника информации. Инкрементирование счетчика 44 происходит по заднему фронту сигнала разрешения обращения к буферу данных на выходе 7. После приема кодового слова счетчик 44 будет содержать двоичный код длины A кодового слова. Этбт код совместно с выходным сигналом тригге15

1810909 ра 12 обеспечивает срабатывание вентиля

23. В ыходной сигнал вентиля 23 через схему

ИЛИ-НЕ 27 закрывает вентиль 31, в результате чего прекращается выдача сигналов с выходов 2, 7, 8, 9, Одновременно сигнал с выхода схемы И 23 открывает вентиль 32 и разрешает установку в «1» триггера 28. N+1й тактовый импульс генератора 15, проходя через схему И 32, формирует на выходе 11 . блока управления сигнал разрешения работы блока селекции ошибок контрольных символов устройства. Этот сигнал через инвертор 33 и схему ИЛИ 24 сбрасывает триггер 29 и включает тем самым на выходе 10 сигнал готовности. По заднему фронту этого же сигнала устанавливается в «1» триггер 28 и закрывает вентиль 32. На этом заканчивается выполнение режима чтения. В режиме коррекции работа блока управления во многом схожа с его работой в режиме чтения.

Различие следующее. После начальной установки приемник информации подает сигнал коррекции на вход 22 и устанавливает в

«1» триггер 13 блока управления. Выходной сигнал этого триггера через усилители 30, 36 формирует на выходах 5, 3 сигналы чтения информации иэ буфера данных и разрешения работы блока фиксации местоположения ошибки. Выходные сигналы схемы И 31, проходя через открытый выходным сигналом триггера 13 вентиль 37, схему задержки

40, схемы ИЛИ 41, 42 формируют на выходах 7, 2, 9 сигналы обращения к буферу данных, сдвига синдромного регистра и синхронизации приемника информации.

После передачи всех и символов кодового слова срабатывает схема И 17, выходной сигнал которой через схему ИЛИ-HE 27 закрывает схему И 31, в результате чего прекращается выдача сигналов с выходов 2, 7, 9. Одновременно выходной сигнал схемы И

17 через инвертор 18, схему ИЛИ 24 сбрасывает триггер 29 и на выходе 20 устанавливается сигнал готовности.

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

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

19, 20 перед чтением кодового слова, сбрасывает синдромный регистр 1 и приводит в начальное состояние блок управления 17, Непосредственно чтение кодового слова начинается после поступления на вход 21 от приемника информации сигнала чтения. После этого формируется последовательность сигналов синхронизации, которые с выхода

24 поступают к источнику кодированных сообщений, За одну команду чтения обеспечивается прием и декодирование одного кодового слова. В ответ на каждый синхросигнал источник сообщений передает один символ. Эти символы со входа 18 корректора ошибок без изменений через блок 12 компенсации ошибок поступают на информационный выход 27 и далее — к приемнику информации в сопровождении сигналов синхронизации на выходе 25 устройства.

Одновременно принимаемые символы записываются в буфер данных 11 и поступают в блок 5 обратной связи для деления на порождающий многочлен. После приема очередного символа блок управления 17 производит сдвиг вправо на один разряд

20 синдромного регистра 1 и инкрементирует на 1 код на адресных входах буфера данных

11. Таким образом в процессе последовательного посимвольного деления принятого кодового слова в регистре 1 накапливаются частичные остатки от деления всех символов кодового слова, образующие в конечном итоге умножений . на х синдром ошибки S = (vgpp + vp ) х modY. После приема всех символов кодового слова блок

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

23 сигнал готовности, на.выход 26 — сигнал

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

Перед началом коррекции приемник информации подает сигнал на вход 19 и при50 водит блок управления s начальное состояние; при этом сигнал сброса ошибки на вход 20 не подается, с тем, чтобы сохранить синдром ошйбки для ее исправления.

Непосредственное осуществление коррек55 ции начинается после-.аодачи .на вход 22 приемником информации, сигнала коррекций. При этом блок управлеиия 17 разрешает работу блока фиксации местоположения ошйбки 10, формирует. сигналы чтения содержимого буфера данных 11, сдвига синд l7

1810909 ромного регистра 1, инкрементирует код на адресных входах буфера данных 11, Считываемое из буфера данных 11 ранее принятое кодовое слово посимвольно передается через блок компенсации ошибки 12, на выход

27 устройства и далее к приемнику информации, Выдаваемые символы сопровождаются сигналами синхронизации на выходе

25 устройства. Одновременно с выдачей очередного символа сдвигается на один разряд синдромный регистр 1 для умножения на х содержащего в нем синдрома ошибки. После того, как в процессе последовательного умножения синдрома будет сформирован вектор ошибки, блок 10 вырабатывает сигнал, который поступит на вход коррекции блока 5 и разорвет обратную связь синдромного регистра 1. Этот же сигнал поступит на вход коррекции блока компенсации ошибки 12 и разрешит передачу вектора ошибки с управляющего выхода синдромного регистра 1 в блок 12 компенсации ошибки, Блок 12 исправляет поступающее в него из буфера данных 11 искаженное кодовое слово и выдает его на выход 27 устройства. Исправленное информационное слово с выхода 27 и сопровожда-. ющие его сигналы синхронизации с выхода

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

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

Для иллюстрации рассмотрим циклический (n, k, m) — код, например код Хзмминга (7, 4, 3), (15, 11, 4), (31, 26, 5), Здесь и — длина кодового слова, k — длина информационного поля, m = n — k — количество контрольных символов. При равновероятном распределении вероятность расположения ошибки в поле контрольных символов для трех выше.указанных кодов Хэмминга составит соответственно 0,43; «. 0,27; 0,16. Таким образом предлагаемое устройство позволит увеличить быстродействие при коррекции соответственно на 43%. 27%, 16%.

Формула изобретения

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

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

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

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

1810909 дЮРА 77юОН

МюЮ ЗДф, g$ +4NHktl фиг.8

Составитель В.Звягинцев

Редактор О.Стенина Техред М.Моргентал . Корректор П.Гереши

Заказ 1447 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

1 .3035, Москва, Ж-35, Раушсыая наб., 4/5

Производственно-издательский комбинат «Патент», г, Ужгород. ул.Гагарина, 101!

L ъ

ОВН6МИ

         

«Interleaver» redirects here. For the fiber-optic device, see optical interleaver.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding^[1][2][3] is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.

The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code, (ECC).^[4][5] The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors. Therefore a reverse channel to request re-transmission may not be needed. The cost is a fixed, higher forward channel bandwidth.

The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first error-correcting code in 1950: the Hamming (7,4) code.^[5]

FEC can be applied in situations where re-transmissions are costly or impossible, such as one-way communication links or when transmitting to multiple receivers in multicast.
Long-latency connections also benefit; in the case of a satellite orbiting Uranus, retransmission due to errors can create a delay of five hours. FEC is widely used in modems and in cellular networks, as well.

FEC processing in a receiver may be applied to a digital bit stream or in the demodulation of a digitally modulated carrier. For the latter, FEC is an integral part of the initial analog-to-digital conversion in the receiver. The Viterbi decoder implements a soft-decision algorithm to demodulate digital data from an analog signal corrupted by noise. Many FEC decoders can also generate a bit-error rate (BER) signal which can be used as feedback to fine-tune the analog receiving electronics.

FEC information is added to mass storage (magnetic, optical and solid state/flash based) devices to enable recovery of corrupted data, and is used as ECC computer memory on systems that require special provisions for reliability.

The maximum proportion of errors or missing bits that can be corrected is determined by the design of the ECC, so different forward error correcting codes are suitable for different conditions. In general, a stronger code induces more redundancy that needs to be transmitted using the available bandwidth, which reduces the effective bit-rate while improving the received effective signal-to-noise ratio. The noisy-channel coding theorem of Claude Shannon can be used to compute the maximum achievable communication bandwidth for a given maximum acceptable error probability. This establishes bounds on the theoretical maximum information transfer rate of a channel with some given base noise level. However, the proof is not constructive, and hence gives no insight of how to build a capacity achieving code. After years of research, some advanced FEC systems like polar code^[3] come very close to the theoretical maximum given by the Shannon channel capacity under the hypothesis of an infinite length frame.

How it works[edit]

ECC is accomplished by adding redundancy to the transmitted information using an algorithm. A redundant bit may be a complex function of many original information bits. The original information may or may not appear literally in the encoded output; codes that include the unmodified input in the output are systematic, while those that do not are non-systematic.

A simplistic example of ECC is to transmit each data bit 3 times, which is known as a (3,1) repetition code. Through a noisy channel, a receiver might see 8 versions of the output, see table below.

Triplet received	Interpreted as
000	0 (error-free)
001	0
010	0
100	0
111	1 (error-free)
110	1
101	1
011	1

This allows an error in any one of the three samples to be corrected by «majority vote», or «democratic voting». The correcting ability of this ECC is:

• Up to 1 bit of triplet in error, or
• up to 2 bits of triplet omitted (cases not shown in table).

Though simple to implement and widely used, this triple modular redundancy is a relatively inefficient ECC. Better ECC codes typically examine the last several tens or even the last several hundreds of previously received bits to determine how to decode the current small handful of bits (typically in groups of 2 to 8 bits).

Averaging noise to reduce errors[edit]

ECC could be said to work by «averaging noise»; since each data bit affects many transmitted symbols, the corruption of some symbols by noise usually allows the original user data to be extracted from the other, uncorrupted received symbols that also depend on the same user data.

• Because of this «risk-pooling» effect, digital communication systems that use ECC tend to work well above a certain minimum signal-to-noise ratio and not at all below it.
• This all-or-nothing tendency – the cliff effect – becomes more pronounced as stronger codes are used that more closely approach the theoretical Shannon limit.
• Interleaving ECC coded data can reduce the all or nothing properties of transmitted ECC codes when the channel errors tend to occur in bursts. However, this method has limits; it is best used on narrowband data.

Most telecommunication systems use a fixed channel code designed to tolerate the expected worst-case bit error rate, and then fail to work at all if the bit error rate is ever worse.
However, some systems adapt to the given channel error conditions: some instances of hybrid automatic repeat-request use a fixed ECC method as long as the ECC can handle the error rate, then switch to ARQ when the error rate gets too high;
adaptive modulation and coding uses a variety of ECC rates, adding more error-correction bits per packet when there are higher error rates in the channel, or taking them out when they are not needed.

Types of ECC[edit]

The two main categories of ECC codes are block codes and convolutional codes.

• Block codes work on fixed-size blocks (packets) of bits or symbols of predetermined size. Practical block codes can generally be hard-decoded in polynomial time to their block length.
• Convolutional codes work on bit or symbol streams of arbitrary length. They are most often soft decoded with the Viterbi algorithm, though other algorithms are sometimes used. Viterbi decoding allows asymptotically optimal decoding efficiency with increasing constraint length of the convolutional code, but at the expense of exponentially increasing complexity. A convolutional code that is terminated is also a ‘block code’ in that it encodes a block of input data, but the block size of a convolutional code is generally arbitrary, while block codes have a fixed size dictated by their algebraic characteristics. Types of termination for convolutional codes include «tail-biting» and «bit-flushing».

There are many types of block codes; Reed–Solomon coding is noteworthy for its widespread use in compact discs, DVDs, and hard disk drives. Other examples of classical block codes include Golay, BCH, Multidimensional parity, and Hamming codes.

Hamming ECC is commonly used to correct NAND flash memory errors.^[6]
This provides single-bit error correction and 2-bit error detection.
Hamming codes are only suitable for more reliable single-level cell (SLC) NAND.
Denser multi-level cell (MLC) NAND may use multi-bit correcting ECC such as BCH or Reed–Solomon.^[7][8] NOR Flash typically does not use any error correction.^[7]

Classical block codes are usually decoded using hard-decision algorithms,^[9] which means that for every input and output signal a hard decision is made whether it corresponds to a one or a zero bit. In contrast, convolutional codes are typically decoded using soft-decision algorithms like the Viterbi, MAP or BCJR algorithms, which process (discretized) analog signals, and which allow for much higher error-correction performance than hard-decision decoding.

Nearly all classical block codes apply the algebraic properties of finite fields. Hence classical block codes are often referred to as algebraic codes.

In contrast to classical block codes that often specify an error-detecting or error-correcting ability, many modern block codes such as LDPC codes lack such guarantees. Instead, modern codes are evaluated in terms of their bit error rates.

Most forward error correction codes correct only bit-flips, but not bit-insertions or bit-deletions.
In this setting, the Hamming distance is the appropriate way to measure the bit error rate.
A few forward error correction codes are designed to correct bit-insertions and bit-deletions, such as Marker Codes and Watermark Codes.
The Levenshtein distance is a more appropriate way to measure the bit error rate when using such codes.
^[10]

Code-rate and the tradeoff between reliability and data rate[edit]

The fundamental principle of ECC is to add redundant bits in order to help the decoder to find out the true message that was encoded by the transmitter. The code-rate of a given ECC system is defined as the ratio between the number of information bits and the total number of bits (i.e., information plus redundancy bits) in a given communication package. The code-rate is hence a real number. A low code-rate close to zero implies a strong code that uses many redundant bits to achieve a good performance, while a large code-rate close to 1 implies a weak code.

The redundant bits that protect the information have to be transferred using the same communication resources that they are trying to protect. This causes a fundamental tradeoff between reliability and data rate.^[11] In one extreme, a strong code (with low code-rate) can induce an important increase in the receiver SNR (signal-to-noise-ratio) decreasing the bit error rate, at the cost of reducing the effective data rate. On the other extreme, not using any ECC (i.e., a code-rate equal to 1) uses the full channel for information transfer purposes, at the cost of leaving the bits without any additional protection.

One interesting question is the following: how efficient in terms of information transfer can an ECC be that has a negligible decoding error rate? This question was answered by Claude Shannon with his second theorem, which says that the channel capacity is the maximum bit rate achievable by any ECC whose error rate tends to zero:^[12] His proof relies on Gaussian random coding, which is not suitable to real-world applications. The upper bound given by Shannon’s work inspired a long journey in designing ECCs that can come close to the ultimate performance boundary. Various codes today can attain almost the Shannon limit. However, capacity achieving ECCs are usually extremely complex to implement.

The most popular ECCs have a trade-off between performance and computational complexity. Usually, their parameters give a range of possible code rates, which can be optimized depending on the scenario. Usually, this optimization is done in order to achieve a low decoding error probability while minimizing the impact to the data rate. Another criterion for optimizing the code rate is to balance low error rate and retransmissions number in order to the energy cost of the communication.^[13]

Concatenated ECC codes for improved performance[edit]

Classical (algebraic) block codes and convolutional codes are frequently combined in concatenated coding schemes in which a short constraint-length Viterbi-decoded convolutional code does most of the work and a block code (usually Reed–Solomon) with larger symbol size and block length «mops up» any errors made by the convolutional decoder. Single pass decoding with this family of error correction codes can yield very low error rates, but for long range transmission conditions (like deep space) iterative decoding is recommended.

Concatenated codes have been standard practice in satellite and deep space communications since Voyager 2 first used the technique in its 1986 encounter with Uranus. The Galileo craft used iterative concatenated codes to compensate for the very high error rate conditions caused by having a failed antenna.

Low-density parity-check (LDPC)[edit]

Low-density parity-check (LDPC) codes are a class of highly efficient linear block
codes made from many single parity check (SPC) codes. They can provide performance very close to the channel capacity (the theoretical maximum) using an iterated soft-decision decoding approach, at linear time complexity in terms of their block length. Practical implementations rely heavily on decoding the constituent SPC codes in parallel.

LDPC codes were first introduced by Robert G. Gallager in his PhD thesis in 1960,
but due to the computational effort in implementing encoder and decoder and the introduction of Reed–Solomon codes,
they were mostly ignored until the 1990s.

LDPC codes are now used in many recent high-speed communication standards, such as DVB-S2 (Digital Video Broadcasting – Satellite – Second Generation), WiMAX (IEEE 802.16e standard for microwave communications), High-Speed Wireless LAN (IEEE 802.11n),^[14] 10GBase-T Ethernet (802.3an) and G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable). Other LDPC codes are standardized for wireless communication standards within 3GPP MBMS (see fountain codes).

Turbo codes[edit]

Turbo coding is an iterated soft-decoding scheme that combines two or more relatively simple convolutional codes and an interleaver to produce a block code that can perform to within a fraction of a decibel of the Shannon limit. Predating LDPC codes in terms of practical application, they now provide similar performance.

One of the earliest commercial applications of turbo coding was the CDMA2000 1x (TIA IS-2000) digital cellular technology developed by Qualcomm and sold by Verizon Wireless, Sprint, and other carriers. It is also used for the evolution of CDMA2000 1x specifically for Internet access, 1xEV-DO (TIA IS-856). Like 1x, EV-DO was developed by Qualcomm, and is sold by Verizon Wireless, Sprint, and other carriers (Verizon’s marketing name for 1xEV-DO is Broadband Access, Sprint’s consumer and business marketing names for 1xEV-DO are Power Vision and Mobile Broadband, respectively).

Local decoding and testing of codes[edit]

Sometimes it is only necessary to decode single bits of the message, or to check whether a given signal is a codeword, and do so without looking at the entire signal. This can make sense in a streaming setting, where codewords are too large to be classically decoded fast enough and where only a few bits of the message are of interest for now. Also such codes have become an important tool in computational complexity theory, e.g., for the design of probabilistically checkable proofs.

Locally decodable codes are error-correcting codes for which single bits of the message can be probabilistically recovered by only looking at a small (say constant) number of positions of a codeword, even after the codeword has been corrupted at some constant fraction of positions. Locally testable codes are error-correcting codes for which it can be checked probabilistically whether a signal is close to a codeword by only looking at a small number of positions of the signal.

Interleaving[edit]

«Interleaver» redirects here. For the fiber-optic device, see optical interleaver.

Interleaving is frequently used in digital communication and storage systems to improve the performance of forward error correcting codes. Many communication channels are not memoryless: errors typically occur in bursts rather than independently. If the number of errors within a code word exceeds the error-correcting code’s capability, it fails to recover the original code word. Interleaving alleviates this problem by shuffling source symbols across several code words, thereby creating a more uniform distribution of errors.^[15] Therefore, interleaving is widely used for burst error-correction.

The analysis of modern iterated codes, like turbo codes and LDPC codes, typically assumes an independent distribution of errors.^[16] Systems using LDPC codes therefore typically employ additional interleaving across the symbols within a code word.^[17]

For turbo codes, an interleaver is an integral component and its proper design is crucial for good performance.^[15][18] The iterative decoding algorithm works best when there are not short cycles in the factor graph that represents the decoder; the interleaver is chosen to avoid short cycles.

Interleaver designs include:

• rectangular (or uniform) interleavers (similar to the method using skip factors described above)
• convolutional interleavers
• random interleavers (where the interleaver is a known random permutation)
• S-random interleaver (where the interleaver is a known random permutation with the constraint that no input symbols within distance S appear within a distance of S in the output).^[19]
• a contention-free quadratic permutation polynomial (QPP).^[20] An example of use is in the 3GPP Long Term Evolution mobile telecommunication standard.^[21]

In multi-carrier communication systems, interleaving across carriers may be employed to provide frequency diversity, e.g., to mitigate frequency-selective fading or narrowband interference.^[22]

Example[edit]

Transmission without interleaving:

Error-free message:                                 aaaabbbbccccddddeeeeffffgggg
Transmission with a burst error:                    aaaabbbbccc____deeeeffffgggg

Here, each group of the same letter represents a 4-bit one-bit error-correcting codeword. The codeword cccc is altered in one bit and can be corrected, but the codeword dddd is altered in three bits, so either it cannot be decoded at all or it might be decoded incorrectly.

With interleaving:

Error-free code words:                              aaaabbbbccccddddeeeeffffgggg
Interleaved:                                        abcdefgabcdefgabcdefgabcdefg
Transmission with a burst error:                    abcdefgabcd____bcdefgabcdefg
Received code words after deinterleaving:           aa_abbbbccccdddde_eef_ffg_gg

In each of the codewords «aaaa», «eeee», «ffff», and «gggg», only one bit is altered, so one-bit error-correcting code will decode everything correctly.

Transmission without interleaving:

Original transmitted sentence:                      ThisIsAnExampleOfInterleaving
Received sentence with a burst error:               ThisIs______pleOfInterleaving

The term «AnExample» ends up mostly unintelligible and difficult to correct.

With interleaving:

Transmitted sentence:                               ThisIsAnExampleOfInterleaving...
Error-free transmission:                            TIEpfeaghsxlIrv.iAaenli.snmOten.
Received sentence with a burst error:               TIEpfe______Irv.iAaenli.snmOten.
Received sentence after deinterleaving:             T_isI_AnE_amp_eOfInterle_vin_...

No word is completely lost and the missing letters can be recovered with minimal guesswork.

Disadvantages of interleaving[edit]

Use of interleaving techniques increases total delay. This is because the entire interleaved block must be received before the packets can be decoded.^[23] Also interleavers hide the structure of errors; without an interleaver, more advanced decoding algorithms can take advantage of the error structure and achieve more reliable communication than a simpler decoder combined with an interleaver^{[citation needed]}. An example of such an algorithm is based on neural network^[24] structures.

Software for error-correcting codes[edit]

Simulating the behaviour of error-correcting codes (ECCs) in software is a common practice to design, validate and improve ECCs. The upcoming wireless 5G standard raises a new range of applications for the software ECCs: the Cloud Radio Access Networks (C-RAN) in a Software-defined radio (SDR) context. The idea is to directly use software ECCs in the communications. For instance in the 5G, the software ECCs could be located in the cloud and the antennas connected to this computing resources: improving this way the flexibility of the communication network and eventually increasing the energy efficiency of the system.

In this context, there are various available Open-source software listed below (non exhaustive).

• AFF3CT(A Fast Forward Error Correction Toolbox): a full communication chain in C++ (many supported codes like Turbo, LDPC, Polar codes, etc.), very fast and specialized on channel coding (can be used as a program for simulations or as a library for the SDR).
• IT++: a C++ library of classes and functions for linear algebra, numerical optimization, signal processing, communications, and statistics.
• OpenAir: implementation (in C) of the 3GPP specifications concerning the Evolved Packet Core Networks.

List of error-correcting codes[edit]

Distance	Code
2 (single-error detecting)	Parity
3 (single-error correcting)	Triple modular redundancy
3 (single-error correcting)	perfect Hamming such as Hamming(7,4)
4 (SECDED)	Extended Hamming
5 (double-error correcting)
6 (double-error correct-/triple error detect)	Nordstrom-Robinson code
7 (three-error correcting)	perfect binary Golay code
8 (TECFED)	extended binary Golay code

• AN codes
• BCH code, which can be designed to correct any arbitrary number of errors per code block.
• Barker code used for radar, telemetry, ultra sound, Wifi, DSSS mobile phone networks, GPS etc.
• Berger code
• Constant-weight code
• Convolutional code
• Expander codes
• Group codes
• Golay codes, of which the Binary Golay code is of practical interest
• Goppa code, used in the McEliece cryptosystem
• Hadamard code
• Hagelbarger code
• Hamming code
• Latin square based code for non-white noise (prevalent for example in broadband over powerlines)
• Lexicographic code
• Linear Network Coding, a type of erasure correcting code across networks instead of point-to-point links
• Long code
• Low-density parity-check code, also known as Gallager code, as the archetype for sparse graph codes
• LT code, which is a near-optimal rateless erasure correcting code (Fountain code)
• m of n codes
• Nordstrom-Robinson code, used in Geometry and Group Theory^[25]
• Online code, a near-optimal rateless erasure correcting code
• Polar code (coding theory)
• Raptor code, a near-optimal rateless erasure correcting code
• Reed–Solomon error correction
• Reed–Muller code
• Repeat-accumulate code
• Repetition codes, such as Triple modular redundancy
• Spinal code, a rateless, nonlinear code based on pseudo-random hash functions^[26]
• Tornado code, a near-optimal erasure correcting code, and the precursor to Fountain codes
• Turbo code
• Walsh–Hadamard code
• Cyclic redundancy checks (CRCs) can correct 1-bit errors for messages at most bits long for optimal generator polynomials of degree , see Mathematics of cyclic redundancy checks#Bitfilters

See also[edit]

• Code rate
• Erasure codes
• Soft-decision decoder
• Burst error-correcting code
• Error detection and correction
• Error-correcting codes with feedback

References[edit]

Further reading[edit]

• MacWilliams, Florence Jessiem; Sloane, Neil James Alexander (2007) [1977]. Written at AT&T Shannon Labs, Florham Park, New Jersey, USA. The Theory of Error-Correcting Codes. North-Holland Mathematical Library. Vol. 16 (digital print of 12th impression, 1st ed.). Amsterdam / London / New York / Tokyo: North-Holland / Elsevier BV. ISBN 978-0-444-85193-2. LCCN 76-41296. (xxii+762+6 pages)
• Clark, Jr., George C.; Cain, J. Bibb (1981). Error-Correction Coding for Digital Communications. New York, USA: Plenum Press. ISBN 0-306-40615-2.
• Arazi, Benjamin (1987). Swetman, Herb (ed.). A Commonsense Approach to the Theory of Error Correcting Codes. MIT Press Series in Computer Systems. Vol. 10 (1 ed.). Cambridge, Massachusetts, USA / London, UK: Massachusetts Institute of Technology. ISBN 0-262-01098-4. LCCN 87-21889. (x+2+208+4 pages)
• Wicker, Stephen B. (1995). Error Control Systems for Digital Communication and Storage. Englewood Cliffs, New Jersey, USA: Prentice-Hall. ISBN 0-13-200809-2.
• Wilson, Stephen G. (1996). Digital Modulation and Coding. Englewood Cliffs, New Jersey, USA: Prentice-Hall. ISBN 0-13-210071-1.
• «Error Correction Code in Single Level Cell NAND Flash memories» 2007-02-16
• «Error Correction Code in NAND Flash memories» 2004-11-29
• Observations on Errors, Corrections, & Trust of Dependent Systems, by James Hamilton, 2012-02-26
• Sphere Packings, Lattices and Groups, By J. H. Conway, Neil James Alexander Sloane, Springer Science & Business Media, 2013-03-09 – Mathematics – 682 pages.

External links[edit]

• Morelos-Zaragoza, Robert (2004). «The Correcting Codes (ECC) Page». Retrieved 5 March 2006.
• lpdec: library for LP decoding and related things (Python)

«Interleaver» redirects here. For the fiber-optic device, see optical interleaver.

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding^[1][2][3] is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.

The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code, (ECC).^[4][5] The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors. Therefore a reverse channel to request re-transmission may not be needed. The cost is a fixed, higher forward channel bandwidth.

The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first error-correcting code in 1950: the Hamming (7,4) code.^[5]

FEC can be applied in situations where re-transmissions are costly or impossible, such as one-way communication links or when transmitting to multiple receivers in multicast.
Long-latency connections also benefit; in the case of a satellite orbiting Uranus, retransmission due to errors can create a delay of five hours. FEC is widely used in modems and in cellular networks, as well.

FEC processing in a receiver may be applied to a digital bit stream or in the demodulation of a digitally modulated carrier. For the latter, FEC is an integral part of the initial analog-to-digital conversion in the receiver. The Viterbi decoder implements a soft-decision algorithm to demodulate digital data from an analog signal corrupted by noise. Many FEC decoders can also generate a bit-error rate (BER) signal which can be used as feedback to fine-tune the analog receiving electronics.

FEC information is added to mass storage (magnetic, optical and solid state/flash based) devices to enable recovery of corrupted data, and is used as ECC computer memory on systems that require special provisions for reliability.

The maximum proportion of errors or missing bits that can be corrected is determined by the design of the ECC, so different forward error correcting codes are suitable for different conditions. In general, a stronger code induces more redundancy that needs to be transmitted using the available bandwidth, which reduces the effective bit-rate while improving the received effective signal-to-noise ratio. The noisy-channel coding theorem of Claude Shannon can be used to compute the maximum achievable communication bandwidth for a given maximum acceptable error probability. This establishes bounds on the theoretical maximum information transfer rate of a channel with some given base noise level. However, the proof is not constructive, and hence gives no insight of how to build a capacity achieving code. After years of research, some advanced FEC systems like polar code^[3] come very close to the theoretical maximum given by the Shannon channel capacity under the hypothesis of an infinite length frame.

How it works[edit]

ECC is accomplished by adding redundancy to the transmitted information using an algorithm. A redundant bit may be a complex function of many original information bits. The original information may or may not appear literally in the encoded output; codes that include the unmodified input in the output are systematic, while those that do not are non-systematic.

A simplistic example of ECC is to transmit each data bit 3 times, which is known as a (3,1) repetition code. Through a noisy channel, a receiver might see 8 versions of the output, see table below.

Triplet received	Interpreted as
000	0 (error-free)
001	0
010	0
100	0
111	1 (error-free)
110	1
101	1
011	1

This allows an error in any one of the three samples to be corrected by «majority vote», or «democratic voting». The correcting ability of this ECC is:

• Up to 1 bit of triplet in error, or
• up to 2 bits of triplet omitted (cases not shown in table).

Though simple to implement and widely used, this triple modular redundancy is a relatively inefficient ECC. Better ECC codes typically examine the last several tens or even the last several hundreds of previously received bits to determine how to decode the current small handful of bits (typically in groups of 2 to 8 bits).

Averaging noise to reduce errors[edit]

ECC could be said to work by «averaging noise»; since each data bit affects many transmitted symbols, the corruption of some symbols by noise usually allows the original user data to be extracted from the other, uncorrupted received symbols that also depend on the same user data.

• Because of this «risk-pooling» effect, digital communication systems that use ECC tend to work well above a certain minimum signal-to-noise ratio and not at all below it.
• This all-or-nothing tendency – the cliff effect – becomes more pronounced as stronger codes are used that more closely approach the theoretical Shannon limit.
• Interleaving ECC coded data can reduce the all or nothing properties of transmitted ECC codes when the channel errors tend to occur in bursts. However, this method has limits; it is best used on narrowband data.

Most telecommunication systems use a fixed channel code designed to tolerate the expected worst-case bit error rate, and then fail to work at all if the bit error rate is ever worse.
However, some systems adapt to the given channel error conditions: some instances of hybrid automatic repeat-request use a fixed ECC method as long as the ECC can handle the error rate, then switch to ARQ when the error rate gets too high;
adaptive modulation and coding uses a variety of ECC rates, adding more error-correction bits per packet when there are higher error rates in the channel, or taking them out when they are not needed.

Types of ECC[edit]

The two main categories of ECC codes are block codes and convolutional codes.

• Block codes work on fixed-size blocks (packets) of bits or symbols of predetermined size. Practical block codes can generally be hard-decoded in polynomial time to their block length.
• Convolutional codes work on bit or symbol streams of arbitrary length. They are most often soft decoded with the Viterbi algorithm, though other algorithms are sometimes used. Viterbi decoding allows asymptotically optimal decoding efficiency with increasing constraint length of the convolutional code, but at the expense of exponentially increasing complexity. A convolutional code that is terminated is also a ‘block code’ in that it encodes a block of input data, but the block size of a convolutional code is generally arbitrary, while block codes have a fixed size dictated by their algebraic characteristics. Types of termination for convolutional codes include «tail-biting» and «bit-flushing».

There are many types of block codes; Reed–Solomon coding is noteworthy for its widespread use in compact discs, DVDs, and hard disk drives. Other examples of classical block codes include Golay, BCH, Multidimensional parity, and Hamming codes.

Hamming ECC is commonly used to correct NAND flash memory errors.^[6]
This provides single-bit error correction and 2-bit error detection.
Hamming codes are only suitable for more reliable single-level cell (SLC) NAND.
Denser multi-level cell (MLC) NAND may use multi-bit correcting ECC such as BCH or Reed–Solomon.^[7][8] NOR Flash typically does not use any error correction.^[7]

Classical block codes are usually decoded using hard-decision algorithms,^[9] which means that for every input and output signal a hard decision is made whether it corresponds to a one or a zero bit. In contrast, convolutional codes are typically decoded using soft-decision algorithms like the Viterbi, MAP or BCJR algorithms, which process (discretized) analog signals, and which allow for much higher error-correction performance than hard-decision decoding.

Nearly all classical block codes apply the algebraic properties of finite fields. Hence classical block codes are often referred to as algebraic codes.

In contrast to classical block codes that often specify an error-detecting or error-correcting ability, many modern block codes such as LDPC codes lack such guarantees. Instead, modern codes are evaluated in terms of their bit error rates.

Most forward error correction codes correct only bit-flips, but not bit-insertions or bit-deletions.
In this setting, the Hamming distance is the appropriate way to measure the bit error rate.
A few forward error correction codes are designed to correct bit-insertions and bit-deletions, such as Marker Codes and Watermark Codes.
The Levenshtein distance is a more appropriate way to measure the bit error rate when using such codes.
^[10]

Code-rate and the tradeoff between reliability and data rate[edit]

The fundamental principle of ECC is to add redundant bits in order to help the decoder to find out the true message that was encoded by the transmitter. The code-rate of a given ECC system is defined as the ratio between the number of information bits and the total number of bits (i.e., information plus redundancy bits) in a given communication package. The code-rate is hence a real number. A low code-rate close to zero implies a strong code that uses many redundant bits to achieve a good performance, while a large code-rate close to 1 implies a weak code.

The redundant bits that protect the information have to be transferred using the same communication resources that they are trying to protect. This causes a fundamental tradeoff between reliability and data rate.^[11] In one extreme, a strong code (with low code-rate) can induce an important increase in the receiver SNR (signal-to-noise-ratio) decreasing the bit error rate, at the cost of reducing the effective data rate. On the other extreme, not using any ECC (i.e., a code-rate equal to 1) uses the full channel for information transfer purposes, at the cost of leaving the bits without any additional protection.

One interesting question is the following: how efficient in terms of information transfer can an ECC be that has a negligible decoding error rate? This question was answered by Claude Shannon with his second theorem, which says that the channel capacity is the maximum bit rate achievable by any ECC whose error rate tends to zero:^[12] His proof relies on Gaussian random coding, which is not suitable to real-world applications. The upper bound given by Shannon’s work inspired a long journey in designing ECCs that can come close to the ultimate performance boundary. Various codes today can attain almost the Shannon limit. However, capacity achieving ECCs are usually extremely complex to implement.

The most popular ECCs have a trade-off between performance and computational complexity. Usually, their parameters give a range of possible code rates, which can be optimized depending on the scenario. Usually, this optimization is done in order to achieve a low decoding error probability while minimizing the impact to the data rate. Another criterion for optimizing the code rate is to balance low error rate and retransmissions number in order to the energy cost of the communication.^[13]

Concatenated ECC codes for improved performance[edit]

Classical (algebraic) block codes and convolutional codes are frequently combined in concatenated coding schemes in which a short constraint-length Viterbi-decoded convolutional code does most of the work and a block code (usually Reed–Solomon) with larger symbol size and block length «mops up» any errors made by the convolutional decoder. Single pass decoding with this family of error correction codes can yield very low error rates, but for long range transmission conditions (like deep space) iterative decoding is recommended.

Concatenated codes have been standard practice in satellite and deep space communications since Voyager 2 first used the technique in its 1986 encounter with Uranus. The Galileo craft used iterative concatenated codes to compensate for the very high error rate conditions caused by having a failed antenna.

Low-density parity-check (LDPC)[edit]

Low-density parity-check (LDPC) codes are a class of highly efficient linear block
codes made from many single parity check (SPC) codes. They can provide performance very close to the channel capacity (the theoretical maximum) using an iterated soft-decision decoding approach, at linear time complexity in terms of their block length. Practical implementations rely heavily on decoding the constituent SPC codes in parallel.

LDPC codes were first introduced by Robert G. Gallager in his PhD thesis in 1960,
but due to the computational effort in implementing encoder and decoder and the introduction of Reed–Solomon codes,
they were mostly ignored until the 1990s.

LDPC codes are now used in many recent high-speed communication standards, such as DVB-S2 (Digital Video Broadcasting – Satellite – Second Generation), WiMAX (IEEE 802.16e standard for microwave communications), High-Speed Wireless LAN (IEEE 802.11n),^[14] 10GBase-T Ethernet (802.3an) and G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable). Other LDPC codes are standardized for wireless communication standards within 3GPP MBMS (see fountain codes).

Turbo codes[edit]

Turbo coding is an iterated soft-decoding scheme that combines two or more relatively simple convolutional codes and an interleaver to produce a block code that can perform to within a fraction of a decibel of the Shannon limit. Predating LDPC codes in terms of practical application, they now provide similar performance.

One of the earliest commercial applications of turbo coding was the CDMA2000 1x (TIA IS-2000) digital cellular technology developed by Qualcomm and sold by Verizon Wireless, Sprint, and other carriers. It is also used for the evolution of CDMA2000 1x specifically for Internet access, 1xEV-DO (TIA IS-856). Like 1x, EV-DO was developed by Qualcomm, and is sold by Verizon Wireless, Sprint, and other carriers (Verizon’s marketing name for 1xEV-DO is Broadband Access, Sprint’s consumer and business marketing names for 1xEV-DO are Power Vision and Mobile Broadband, respectively).

Local decoding and testing of codes[edit]

Sometimes it is only necessary to decode single bits of the message, or to check whether a given signal is a codeword, and do so without looking at the entire signal. This can make sense in a streaming setting, where codewords are too large to be classically decoded fast enough and where only a few bits of the message are of interest for now. Also such codes have become an important tool in computational complexity theory, e.g., for the design of probabilistically checkable proofs.

Locally decodable codes are error-correcting codes for which single bits of the message can be probabilistically recovered by only looking at a small (say constant) number of positions of a codeword, even after the codeword has been corrupted at some constant fraction of positions. Locally testable codes are error-correcting codes for which it can be checked probabilistically whether a signal is close to a codeword by only looking at a small number of positions of the signal.

Interleaving[edit]

«Interleaver» redirects here. For the fiber-optic device, see optical interleaver.

Interleaving is frequently used in digital communication and storage systems to improve the performance of forward error correcting codes. Many communication channels are not memoryless: errors typically occur in bursts rather than independently. If the number of errors within a code word exceeds the error-correcting code’s capability, it fails to recover the original code word. Interleaving alleviates this problem by shuffling source symbols across several code words, thereby creating a more uniform distribution of errors.^[15] Therefore, interleaving is widely used for burst error-correction.

The analysis of modern iterated codes, like turbo codes and LDPC codes, typically assumes an independent distribution of errors.^[16] Systems using LDPC codes therefore typically employ additional interleaving across the symbols within a code word.^[17]

For turbo codes, an interleaver is an integral component and its proper design is crucial for good performance.^[15][18] The iterative decoding algorithm works best when there are not short cycles in the factor graph that represents the decoder; the interleaver is chosen to avoid short cycles.

Interleaver designs include:

• rectangular (or uniform) interleavers (similar to the method using skip factors described above)
• convolutional interleavers
• random interleavers (where the interleaver is a known random permutation)
• S-random interleaver (where the interleaver is a known random permutation with the constraint that no input symbols within distance S appear within a distance of S in the output).^[19]
• a contention-free quadratic permutation polynomial (QPP).^[20] An example of use is in the 3GPP Long Term Evolution mobile telecommunication standard.^[21]

In multi-carrier communication systems, interleaving across carriers may be employed to provide frequency diversity, e.g., to mitigate frequency-selective fading or narrowband interference.^[22]

Example[edit]

Transmission without interleaving:

Error-free message:                                 aaaabbbbccccddddeeeeffffgggg
Transmission with a burst error:                    aaaabbbbccc____deeeeffffgggg

Here, each group of the same letter represents a 4-bit one-bit error-correcting codeword. The codeword cccc is altered in one bit and can be corrected, but the codeword dddd is altered in three bits, so either it cannot be decoded at all or it might be decoded incorrectly.

With interleaving:

Error-free code words:                              aaaabbbbccccddddeeeeffffgggg
Interleaved:                                        abcdefgabcdefgabcdefgabcdefg
Transmission with a burst error:                    abcdefgabcd____bcdefgabcdefg
Received code words after deinterleaving:           aa_abbbbccccdddde_eef_ffg_gg

In each of the codewords «aaaa», «eeee», «ffff», and «gggg», only one bit is altered, so one-bit error-correcting code will decode everything correctly.

Transmission without interleaving:

Original transmitted sentence:                      ThisIsAnExampleOfInterleaving
Received sentence with a burst error:               ThisIs______pleOfInterleaving

The term «AnExample» ends up mostly unintelligible and difficult to correct.

With interleaving:

Transmitted sentence:                               ThisIsAnExampleOfInterleaving...
Error-free transmission:                            TIEpfeaghsxlIrv.iAaenli.snmOten.
Received sentence with a burst error:               TIEpfe______Irv.iAaenli.snmOten.
Received sentence after deinterleaving:             T_isI_AnE_amp_eOfInterle_vin_...

No word is completely lost and the missing letters can be recovered with minimal guesswork.

Disadvantages of interleaving[edit]

Use of interleaving techniques increases total delay. This is because the entire interleaved block must be received before the packets can be decoded.^[23] Also interleavers hide the structure of errors; without an interleaver, more advanced decoding algorithms can take advantage of the error structure and achieve more reliable communication than a simpler decoder combined with an interleaver^{[citation needed]}. An example of such an algorithm is based on neural network^[24] structures.

Software for error-correcting codes[edit]

Simulating the behaviour of error-correcting codes (ECCs) in software is a common practice to design, validate and improve ECCs. The upcoming wireless 5G standard raises a new range of applications for the software ECCs: the Cloud Radio Access Networks (C-RAN) in a Software-defined radio (SDR) context. The idea is to directly use software ECCs in the communications. For instance in the 5G, the software ECCs could be located in the cloud and the antennas connected to this computing resources: improving this way the flexibility of the communication network and eventually increasing the energy efficiency of the system.

In this context, there are various available Open-source software listed below (non exhaustive).

• AFF3CT(A Fast Forward Error Correction Toolbox): a full communication chain in C++ (many supported codes like Turbo, LDPC, Polar codes, etc.), very fast and specialized on channel coding (can be used as a program for simulations or as a library for the SDR).
• IT++: a C++ library of classes and functions for linear algebra, numerical optimization, signal processing, communications, and statistics.
• OpenAir: implementation (in C) of the 3GPP specifications concerning the Evolved Packet Core Networks.

List of error-correcting codes[edit]

Distance	Code
2 (single-error detecting)	Parity
3 (single-error correcting)	Triple modular redundancy
3 (single-error correcting)	perfect Hamming such as Hamming(7,4)
4 (SECDED)	Extended Hamming
5 (double-error correcting)
6 (double-error correct-/triple error detect)	Nordstrom-Robinson code
7 (three-error correcting)	perfect binary Golay code
8 (TECFED)	extended binary Golay code

• AN codes
• BCH code, which can be designed to correct any arbitrary number of errors per code block.
• Barker code used for radar, telemetry, ultra sound, Wifi, DSSS mobile phone networks, GPS etc.
• Berger code
• Constant-weight code
• Convolutional code
• Expander codes
• Group codes
• Golay codes, of which the Binary Golay code is of practical interest
• Goppa code, used in the McEliece cryptosystem
• Hadamard code
• Hagelbarger code
• Hamming code
• Latin square based code for non-white noise (prevalent for example in broadband over powerlines)
• Lexicographic code
• Linear Network Coding, a type of erasure correcting code across networks instead of point-to-point links
• Long code
• Low-density parity-check code, also known as Gallager code, as the archetype for sparse graph codes
• LT code, which is a near-optimal rateless erasure correcting code (Fountain code)
• m of n codes
• Nordstrom-Robinson code, used in Geometry and Group Theory^[25]
• Online code, a near-optimal rateless erasure correcting code
• Polar code (coding theory)
• Raptor code, a near-optimal rateless erasure correcting code
• Reed–Solomon error correction
• Reed–Muller code
• Repeat-accumulate code
• Repetition codes, such as Triple modular redundancy
• Spinal code, a rateless, nonlinear code based on pseudo-random hash functions^[26]
• Tornado code, a near-optimal erasure correcting code, and the precursor to Fountain codes
• Turbo code
• Walsh–Hadamard code
• Cyclic redundancy checks (CRCs) can correct 1-bit errors for messages at most bits long for optimal generator polynomials of degree , see Mathematics of cyclic redundancy checks#Bitfilters

See also[edit]

• Code rate
• Erasure codes
• Soft-decision decoder
• Burst error-correcting code
• Error detection and correction
• Error-correcting codes with feedback

References[edit]

Further reading[edit]

• MacWilliams, Florence Jessiem; Sloane, Neil James Alexander (2007) [1977]. Written at AT&T Shannon Labs, Florham Park, New Jersey, USA. The Theory of Error-Correcting Codes. North-Holland Mathematical Library. Vol. 16 (digital print of 12th impression, 1st ed.). Amsterdam / London / New York / Tokyo: North-Holland / Elsevier BV. ISBN 978-0-444-85193-2. LCCN 76-41296. (xxii+762+6 pages)
• Clark, Jr., George C.; Cain, J. Bibb (1981). Error-Correction Coding for Digital Communications. New York, USA: Plenum Press. ISBN 0-306-40615-2.
• Arazi, Benjamin (1987). Swetman, Herb (ed.). A Commonsense Approach to the Theory of Error Correcting Codes. MIT Press Series in Computer Systems. Vol. 10 (1 ed.). Cambridge, Massachusetts, USA / London, UK: Massachusetts Institute of Technology. ISBN 0-262-01098-4. LCCN 87-21889. (x+2+208+4 pages)
• Wicker, Stephen B. (1995). Error Control Systems for Digital Communication and Storage. Englewood Cliffs, New Jersey, USA: Prentice-Hall. ISBN 0-13-200809-2.
• Wilson, Stephen G. (1996). Digital Modulation and Coding. Englewood Cliffs, New Jersey, USA: Prentice-Hall. ISBN 0-13-210071-1.
• «Error Correction Code in Single Level Cell NAND Flash memories» 2007-02-16
• «Error Correction Code in NAND Flash memories» 2004-11-29
• Observations on Errors, Corrections, & Trust of Dependent Systems, by James Hamilton, 2012-02-26
• Sphere Packings, Lattices and Groups, By J. H. Conway, Neil James Alexander Sloane, Springer Science & Business Media, 2013-03-09 – Mathematics – 682 pages.

External links[edit]

• Morelos-Zaragoza, Robert (2004). «The Correcting Codes (ECC) Page». Retrieved 5 March 2006.
• lpdec: library for LP decoding and related things (Python)

Блочные корректирующие коды широко применяются в различных радиоэлектронных устройствах [1, 2]. При этом отсутствует описание синтеза этих устройств в известной программе моделирования MicroCap 9 [3]. Почти все блочные коды относятся к разделимым, или систематическим, то есть их комбинации состоят из двух частей: информационной и проверочной. Информационные и проверочные разряды занимают одни и те же определенные позиции.

Разделимые коды обозначают в виде (n,k)-кодов (n — «значность» кода; k — число информационных разрядов), r = n–k — число проверочных разрядов.

Наиболее часто применяются линейные систематические коды. Для систематического (n,k)-кода любая кодовая комбинация записывается в виде:

X = (x₁, …, x_i, …, x_k; z₁, …, z_j, …, z_r),

где x₁, …, x_i, …, x_k — информационная комбинация; z₁, …, z_j, …, z_r — проверочные символы.

Линейные коды полностью определяются k линейно-независимыми кодовыми комбинациями. Совокупность этих k‑комбинаций, называемых базисными, образует порождающую матрицу кода. Часто используется каноническая форма порождающей матрицы:

Порождающая матрица полностью задает код, так как все кодовые комбинации (за исключением нулевой) могут быть получены путем посимвольного сложения по модулю двух входящих в порождающую матрицу первой, второй, …, k‑ой базисных комбинаций. Образование кодовых комбинаций происходит при линейном сложении различного числа базисных комбинаций, что и определяет название линейных кодов. Для того чтобы каноническая порождающая матрица определяла код с кодовым расстоянием d_min, необходимо и достаточно, чтобы сумма любых l строк избыточной матрицы образовывала r‑символьную комбинацию, вес которой (количество отличных от нуля символов):

w ≥ d_min–l.

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

Рассмотрим линейный (7,4)-код с кодовым расстоянием d_min = 3. Порождающая матрица для этого кода может быть записана в виде:

Легко убедиться, что сумма любых l‑строк (l = 1, 2, …, k) избыточной подматрицы дает комбинацию, вес которой не менее 3–l, то есть порождает код с d_min = 3. Матрица содержит четыре из 15 ненулевых комбинаций кода. Остальные 11 комбинаций могут быть получены сложением базисных комбинаций. Например, кодовая комбинация, соответствующая информационной (1011), получается посимвольным сложением 1‑й, 3‑й и 4‑й строк и имеет вид (1011100).

Достоинством систематических кодов является их сравнительно простая техническая реализация. На структурной схеме (рис. 1) представлено кодирующее устройство (7,4)-кода, состоящее из 7‑разрядного регистра сдвига и трех сумматоров по модулю 2.

Регистр содержит две части: информационную (четыре ячейки) и проверочную (три ячейки). Каждый сумматор служит для формирования проверочного символа, находящегося на определенной позиции. Подключение информационных ячеек регистра к соответствующим сумматорам выполнено по правилам построения корректирующего (7,4)-кода:

R₁ = i₁⊕i₂⊕i₃,

R₂ = i₂⊕i₃⊕i₄,

R₃ = i₁⊕i₂⊕i₄.

Рассмотрим принцип работы кодера. Первичная кодовая комбинация записывается параллельно в четыре информационные ячейки регистра. Одновременно с этим в трех сумматорах по модулю 2 формируются три проверочных символа, которые записываются в три проверочные ячейки регистра. Полученная кодовая комбинация выводится из регистра с помощью подачи тактовых импульсов от генератора тактовых импульсов. После семи тактовых импульсов кодовая комбинация будет выведена из регистра. Далее регистр подготавливается к записи и формированию следующей кодовой комбинации. Сформированные комбинации поступают к модулятору передатчика.

На рис. 2 приведена схема кодера, синтезированная в среде MicroCap 9. С целью упрощенного получения в схеме информационных символов регистр, содержащий четыре информационные ячейки, заменен на четыре цифровых переключателя i₁–i₄. Проверочные ячейки R₁–R₃ выполнены на двухвходовых сумматорах по модулю 2. На схеме индикаторы красного цвета показывают логическую единицу информационных и проверочных символов. Индикаторы черного цвета соответствуют логическому нулю.

Генератор тактовых импульсов ввиду отсутствия сдвигающего регистра заменен на семь импульсных генераторов V1–V7, формирующих импульсы длительностью 10 мкс и задержанных друг относительно друга на 10 мкс.

Буферные блоки B1–B7 предназначены для согласования аналоговой части схемы с цифровой схемой, которая содержит двухвходовые элементы И, а также элемент ИЛИ с девятью входами. В нем используются семь входов по числу символов корректирующего (7,4)-кода.

На рис. 3 приведены осциллограммы на выходах импульсных генераторов V1–V7, выходе элемента ИЛИ и выходе фазового манипулятора PSK.

Рассмотрим работу декодера (7,4)-кода (рис. 4). Декодер (7,4)-кода состоит из семи триггерных ячеек, трех сумматоров по модулю 2, анализатора ошибок и корректора ошибок. По фронту стробирующего импульса последовательность символов принятой от демодулятора кодовой комбинации записывается в семь ячеек регистра, и с помощью сумматоров проводится проверка на четность для информационных и проверочных символов по следующим правилам:

S₁ = R₁⊕i₁⊕i₃⊕i₄,

S₂ = R₂⊕i₁⊕i₂⊕i₃,

S₃ = R₃⊕i₁⊕i₂⊕i₄.

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

На рис. 5а приведены схема блока ввода ошибок в информационные и проверочные символы и схема анализатора ошибок в среде MicroCap 9.

На рис. 5а показана безошибочная передача символов (7,4)-кода: 1010 001. Безошибочная передача символов подтверждается отсутствием ввода ошибок в блоке (нулевое положение цифровых ключей i₁–i₄, R₁–R₃), индикацией принятых символов, совпадающих с переданными, нулевым синдромом «000», индикатором «ошибки нет».

На рис. 5б представлена передача символов (7,4)-кода с введенной ошибкой в символе i₁. В блоке ввода ошибок пунктиром показан цифровой ключ i₁ в единичном положении. Это означает ввод ошибки в символ i₁, что и характеризует принятый символ i₁ (выделен пунктиром). В результате формируется синдром вида (1,1,1) и формируется логическая единица на выходе i₁ анализатора ошибок.

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

Таблица. Конфигурация ошибок

Синдром	001	010	011	100
Конфигурация ошибок	01000000	00100000	00010000	00001000
Ошибочный символ	R3	R2	i2	R1
Синдром	101	110	111	000
Конфигурация ошибок	00000100	00000010	00000001	10000000
Ошибочный символ	i4	i3	i1	Нет ошибок

На рис. 6 приведен другой пример одиночной ошибки в проверочном символе R₂.

В переданном коде 0011 011 цифровым ключом R₂ в блоке ввода ошибок введена ошибка в символ R₂: 0011 001. Она зафиксирована в принятых символах, в синдроме вида (0,1,0) и при формировании логической единицы на выходе R₂ анализатора ошибок. В результате корректирующий (7,4)-код на выходе корректора исправляет ошибку в символе R₂.

Таким образом, в соответствии с текущей конфигурацией ошибок блок коррекции формирует управляющий сигнал, задающий инверсию для бита в позиции, соответствующей ошибочному символу. Выполнен блок коррекции ошибок по числу символов блочного корректирующего (7,4)-кода на семи сумматорах по модулю 2.

В случае одиночной ошибки на выходе корректора декодера формируется верная кодовая последовательность, а на выходе анализатора ошибок формируется логическая единица, которая обозначает в данном случае ошибочный символ. На рис. 7 представлена схема кодера и декодера блочного корректирующего (7,4)-кода в среде MicroCap 9.

На рис. 7 в блоке ввода ошибок цифровой ключ i₃ показан в единичном положении. Это означает в данном случае ввод ошибки в символ i₃, что и характеризует ошибочный принятый символ i₃. В результате формируется синдром вида (1,1,0) и формируется логическая единица на выходе i₃ анализатора ошибок. Корректор исправляет эту ошибку.

В правом верхнем углу на рис. 7 пунктиром выделен и в увеличенном виде показан блок PSK — фазовый манипулятор несущей частоты 400 кГц по закону блочного корректирующего (7,4)-кода для данной кодовой комбинации 0110 101. Осциллограммы кодовой комбинации 0110 101 и соответствующая ей фазовая манипуляция несущего колебания приведены на рис. 8.

Представленный в работе метод реализации (7,4)-кода можно использовать для синтеза других типов корректирующих (n,k)-кодов. Разработанная модель дает возможность проводить широкий круг исследований кодера и декодера корректирующего (7,4)-кода, устройств блочных корректирующих (n,k)-кодов. Синтезированная модель корректирующего (7,4)-кода в среде MicroCap 9 актуальна для разработчиков соответствующей аппаратуры и может быть использована при обучении студентов радиотехнических специальностей.