Восстановить при помощи алгоритма рида соломона исходное сообщение длины 3 в z5

Обновлено: 02.07.2024

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

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

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

Наиболее важными расширениями кодов Рида-Соломона являются расширения на один символ, так как среди них содержатся коды длины а во многих приложениях в качестве длины кода используется именно степень двойки. Мы начнем с этого случая, так как он претставляет практический интерес из-за простоты декодера и так как его лет ко объяспить.

В рассматриваемом коде спектральные компоненты равны нулю и единственную проверку на четность дает символ Равенство нулю компонент гарантирует, что минимальное расстояние в коде равно , и поэтому код позволяет исправлять и обнаруживать I ошибок. Блок

из компонент синдрома начинается с компоненты равной и заканчивается компонентой равной Предположим, что произошло не более ошибок, и проведем итерации алгоритма Берлекэмпа-Месси от до Если и невязка равна нулю, то, согласно теореме 7.5.3, во внутреннем векторе произошло не более ошибок и вычисленное значение многочлена локаторов ошибок правильно. В противном случае во внутреннем векторе произошло ошибок, и, следовательно, символ правилен. Дополнительная компонуй синдрома позволяет продолжить алгоритм Берлекэмпа-Месси еще на один шаг, так что полное число итераций равно , и поэтому найден многочлен локаторов ошибок. Декодер для расширенного на одну позицию кода Рида-Соломона показан на рис. 9.5.

Декодер для расширенного на два символа кода Рида-Соломона более сложен и описать его труднее. Предположим, что произошло не более ошибок. В нашем распоряжении имеются компонент внутреннего синдрома, начиная с компоненты равной Согласно теореме 7.5.3, воспользуемся ими для исправления ошибок во внутреннем векторе и обнаружения ошибок. Иначе говоря, начиная с и выполняя итераций алгоритма Берлекэмпа-Месси, найдем многочлен локаторов ошибок. Если то сделаем еще две итерации и остановимся, если хотя бы одна из невязок или отлична от нуля. Если обе невязки равны нулю, то во внутреннем векторе произошло не более ошибок. В этом случае многочлен локаторов ошибок вычислен правильпо и может быть использован для дальнейшего исправления ошибок во внутреннем векторе. Так как полезная информация может быть полностью выделена из внутреннего вектора, то декодирование закончено. В противном случае внутренний вектор содержит или ошибок, и поэтому искажено не более одного граничного символа. Следовательно, хотя бы одна из компонент и синдрома правильна, а если все ошибки произошли во внутреннем векторе, то они правильны обе. Присоединяя сначала одну, а затем вторую из них к остальным компонентам синдрома, получим два блока по символов, хотя бы один из которых содержит правильных компонент синдрома.

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

Рис. 9.5. (см. скан) Декодер для расширенного на один символ кода Рида-Соломона.

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

Описанная процедура декодирования все же дважды обращается к алгоритму Берлекэмпа-Месси. Такое описание выбрано из соображений простоты объяснения; процедуру можно сделать более компактной.

устройствах памяти (включая магнитные ленты, CD, DVD, штриховые коды, и т.д.);
беспроводных или мобильных коммуникациях (включая сотовые телефоны, микроволновые каналы и т.д.);
спутниковых коммуникациях;
цифровом телевидении / DVB (digital video broadcast );
скоростных модемах, таких как ADSL , xDSL и т.д.

Рис. 4.3. Несовершенство кода, как функция размера информационного блока для разных задач и алгоритмов

Свойства кодов Рида-Соломона

Коды Рида-Соломона являются субнабором кодов BCH и представляют собой линейные блочные коды. Код Рида-Соломона специфицируются как RS(n,k) s -битных символов.

Это означает, что кодировщик воспринимает k информационных символов по s битов каждый и добавляет символы четности для формирования n символьного кодового слова. Имеется nk символов четности по s битов каждый. Декодер Рида-Соломона может корректировать до t символов, которые содержат ошибки в кодовом слове, где 2t = n–k .

Диаграмма, представленная ниже, показывает типовое кодовое слово Рида-Соломона:

n = 255, k = 223, s = 8

При размере символа s , максимальная длина кодового слова ( n ) для кода Рида-Соломона равна n = 2 s – 1 .

Коды Рида-Соломона могут быть в принципе укорочены путем обнуления некоторого числа информационных символов на входе кодировщика (передавать их в этом случае не нужно). При передаче данных декодеру эти нули снова вводятся в массив.

Пример. Код (255, 223), описанный выше, может быть укорочен до (200, 168). Кодировщик будет работать с блоком данных 168 байт, добавит 55 нулевых байт, сформирует кодовое слово (255, 223) и передаст только 168 информационных байт и 32 байта четности .

Объем вычислительной мощности, необходимой для кодирования и декодирования кодов Рида-Соломона, зависит от числа символов четности . Большое значение t означает, что большее число ошибок может быть исправлено, но это потребует большей вычислительной мощности по сравнению с вариантом при меньшем t .

Ошибки в символах

Одна ошибка в символе происходит, когда 1 бит символа оказывается неверным или когда все биты неверны.

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

Декодирование

Когда кодовое слово декодируется, возможны три варианта.

Если 2s + r ( s ошибок, r потерь), тогда исходное переданное кодовое слово всегда будет восстановлено. В противном случае
Декодер детектирует ситуацию, когда он не может восстановить исходное кодовое слово. или
Декодер некорректно декодирует и неверно восстановит кодовое слово без какого-либо указания на этот факт.

Вероятность каждого из этих вариантов зависит от типа используемого кода Рида-Соломона, а также от числа и распределения ошибок.

Объяснение кода Рида-Соломона, написанного для программистов

Аннотация:Недавно я увидел код RS и нашел его довольно интересным. Я нашел некоторые материалы для изучения и обнаружил, что программистам будет легче начать с этой статьи. Прочитав его, я захотел перевести его и посмотреть, насколько я понял, поэтому я придумал эту статью. Есть некоторые ошибки в этой статье и некоторые опечатки. Если вам интересно, лучше прочитать оригинальный текст :)

Коды коррекции ошибок Рида-Соломона (далее называемые кодами RS) широко используются в хранилищах данных (таких как CD) и в приложениях передачи. Однако в этих приложениях кодовые слова скрыты в электронном устройстве, поэтому невозможно понять, как они выглядят и насколько они эффективны. Некоторые сложные конструкции штрих-кодов также используют коды RS, которые могут раскрыть все детали.Это очень интересный способ для энтузиастов, которые хотят получить информацию из первых рук о том, как эта технология работает.
В этой статье я пытаюсь представить основные принципы кодов RS с точки зрения программиста (не математика). Я буду использовать популярный QR-код в качестве примера, чтобы представить. Я выбрал Python (в основном потому, что написанный мною код выглядит аккуратно и красиво), но я также представлю некоторые менее очевидные возможности Python, чтобы те, кто не знаком с Python, могли его понять. Используемая в нем математика предъявляет определенные требования к читателям и обычно преподается в университетах, но ее должны понимать люди, хорошо разбирающиеся в алгебре средней школы.

1. Структура QR-кода

1.1 Маска

Причина необходимости обработки маски состоит в том, чтобы избегать таких фигур, как локаторные узоры или большие пустые области в области данных, которые могут запутать сканер. Процесс маскирования инвертирует некоторые модули (белый становится черным, а черный становится белым), оставляя другие модули без изменений.
Обратитесь к рисунку ниже, красная область кодируется с помощью шаблона фиксированной маски, и информация о формате маски области данных (черно-белая часть) сохраняется. Когда QR-код создан, кодировщик пытается выбрать шаблон маски, который минимизирует нежелательные функции. Информация о выбранном режиме маски будет сохранена в информации о формате (красная область), чтобы декодер знал, какой из них использовать. Светло-серая область - это фиксированный шаблон, который не содержит никакой информации. Кроме того, в режиме локатора он также содержит линейку (timing patterns Справочное объяснение）。Исходное изображение

1.2 Формат информации

Существует еще одна распознаваемая копия информации о формате, поэтому, даже если один из них будет уничтожен, все равно есть шанс быть распознанным. Копия делится на две части, размещается сбоку от двух других локаторов, а также читается против часовой стрелки (вверх по левому нижнему локатору, а затем по верхнему правому краю локатора слева направо).
Первые 2 формата информацииbitsПриведен уровень исправления ошибок, используемый для данных. QR-код этого размера содержит 26 байт (bytes,1 byte = 8 bits) Информация, некоторые из которых используются для хранения исходных данных, а некоторые используются для хранения контрольных кодов, как показано в следующей таблице. Первый столбец слева - это просто простое имя для уровня исправления ошибок.

Уровень исправления ошибок	Индикатор уровня	Коды исправления ошибок	Количество оригинальных байтов данных
L	01	7	19
M	00	10	16
Q	11	13	13
H	10	17	9

Следующие 3 в формате информацииbitsИспользуется для указания шаблона маски, используемого для области данных. Образец определен способом пения 6x6, повторяемым по мере необходимости, чтобы покрыть всю область. Шаблон показан ниже, включая соответствующую математическую формулу, чтобы указать, является ли каждый модуль (в маске) черным (i и j - числа, начинающиеся с 0 в строках и столбцах, считая от верхнего левого угла)Исходное изображение

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

1.3 Данные

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

Биты данных начинаются с правого нижнего угла и поднимаются зигзагообразно вдоль двух крайних правых столбцов. Первые три байта: 01000000 11010010 01110101 (Примечание: см. Небольшую стрелку в правом нижнем углу рисунка). Следующие два столбца читаются сверху вниз, поэтому следующий байт - 01000111. Прочитав до конца, прочитайте следующие два столбца снизу вверх . таким образом, прочитайте до самого левого столбца (если необходимо, пропустите схему синхронизации). Ниже приводится полное шестнадцатеричное представление данных:

Первоначальная информация: 40 d2 75 47 76 17 32 06 27 26 96 c6 c6 96 70 ec
Исправление ошибок: bc 2a 90 13 6b af ef fd 4b e0

1.4 Декодирование

Название проекта	Индикатор режима	Длина в байтах	Количество байтов данных
цифровой	0001	10	10 bits per 3 digits
буква и цифра	0010	9	11 bits per 2 characters
байт	0100	8	8 bits per character
китайский символ	1000	8	13 bits per character

Длина байтов действительна только для маленьких QR-кодов

2. Код БЧХ

2.1 Обнаружение ошибок МПБ

Следующая функция Python реализует этот процесс

4.2.2 Обработка ошибок (так же, как python, опущено)

4.2.3 Генератор РС полином

Код RS использует аналогичный код BCH Генератор полинома , Умножить (x-α ^ n). Например:

g(x) = (x - α^0) (x - α^1) (x - α^2) (x - α^3) = 01 x^4 + 0f x^3 + 36 x^2 + 78 x^1 + 40

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

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

4.2.4. Полиномиальное деление

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

Соедините остаток и исходные данные, чтобы получить закодированные данные 12 34 56 37 e6 78 d9. Этот вид целочисленного деления неэффективен из-за множества циклов соглашения, необходимых в реализации алгоритма.Синтетическое подразделение (синтетическое подразделение)Это более эффективный алгоритм. Следующий код представляет собой расширенную реализацию алгоритма до полинома GF (2 ^ p):

4.2.5 Функция кодирования

4.3.2 Расчет синдрома

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

Следующий код используется для автоматической проверки правильности информации:

=== Начало аннотации ===
Полученные данные r (x) получают путем объединения кодированных данных (кодовое слово кода RS) c (x) и ошибки e (x):
r(x) = c(x) + e(x)
Помните v = nsym, потому что c (x) является корнем полинома генератора в α ^ 0, α ^ 1, α ^ 2, . α ^ (v-1) (см. Определение генератора полинома, чтобы увидеть, Обратите внимание, что + на самом деле -), и c (x) может быть выражено как q (x) * g (x) (если вы не понимаете, пожалуйста, обратитесь к аннотациям в разделе 2.1), поэтому результат оценки c (x) здесь должен быть Это 0.
Если значение r (x) равно 0, это означает, что e (x) также равно 0, что указывает на то, что оно либо в порядке, либо ошибочно, что его вообще нельзя найти (это другое кодовое слово). Если r (x) не равно 0, то синдром S является точно значением всех e (x):
S[0] = e(1), S[1] = e(α^1), S[2] = e(α^2), . S[v-1] = e(α^(v-1))
Если количество неправильных кодовых слов не превышает v / 2, информация может быть восстановлена через S.
=== Конец аннотации ===

4.3.3 Устранение (стирание) исправление

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

Наконец, алгоритм Форни реализует шаг 4. Следующая функция содержит алгоритм для достижения исправления и исключения:

Python отмечает:Эта функция использует [:: - 1] для изменения порядка элементов списка.

Тест кода выглядит следующим образом:

4.3.4 Исправление ошибок

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

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

Аннотация: я не рассматривал этот алгоритм более подробно: в общем, он использует тождество Ньютона (составленное в соответствии с 4.3.3), чтобы сгенерировать полином местоположения ошибки, а затем оценить его, чтобы получить местоположение ошибки. Для более подробной информации, пожалуйста, обратитесь кAN2407.pdf

Этот метод неэффективен, и поиск Chien является более эффективным алгоритмом.

4.3.5 Устранение и исправление ошибок

Синдром Форнея может быть использован для замены синдрома при обычном поиске местоположения ошибки.
Следующая функция rs_correct_errata дает полный процесс, используя -1 в позиции, где исключается msg_in.

Замечание по Python: два массива erase_pos и err_pos связаны операцией +.

Это последний сегмент, необходимый для реализации полнофункционального декодера RS исправления ошибок / устранения ошибок. Если вы хотите пойти глубже, оригинальный автор рекомендует книгу "Algebraic Codes for Data Transmission》

5 Упакуйте экземпляр

В следующем примере показано, как использовать код выше для кодирования и декодирования:

ГОСТ

Кодирование Рида-Соломона

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

Как и у всех помехоустойчивых кодов, исправляющая способность кода Рида-Соломона основана на добавлении избыточности в информационные данные. Коды были разработаны в 1960 году в Массачусетском технологическом институте Ирвином Ридом и Густавом Соломоном и являются частным случаем БЧХ-кодов (кодов Боуза-Чоудхури-Хоквингема).

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

Коды Рида-Соломона используются в следующих современных системах цифровой передачи и хранения информации:

спутниковая связь;
мобильная связь;
цифровое DVB-телевидение;
модемы передачи данных;
запись и хранение данных на CD и DVD дисках;
штрих-коды и QR-коды.

При передаче информации в каналах связи возникают помехи, при хранении информации на DVD дисках могут появиться царапины, QR-код может нечётко пропечататься, и всё это приводит к ошибкам в первоначальной информации. Искажения информации для двоичных сигналов выражаются в замене битов “0” на “1” и наоборот, битов “1” на “0”. Использование кода Рида-Соломона позволяет не только обнаружить факт искажения первоначальной информации, но и локализовать искажённую позицию, а для двоичной информации это равносильно исправлению ошибки. На практике впервые коды Рида-Соломона были применены при записи информации на лазерные компакт-диски.

Готовые работы на аналогичную тему

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

Реализация кодера и декодера на С++

Также надо обратить внимание на то, что существуют две разновидности кодов Рида-Соломона – систематический и несистематический. При систематическом кодировании исходные $k$ информационных символов остаются неизменными, а проверочные $m$ символов добавляются в конце информационного слова. Поэтому при декодировании такого кода, в случае если ошибки в текущем блоке не обнаруживаются, то просто отбрасываются проверочные символы, а остаются чистые информационные символы. Если ошибки были обнаружены, то они исправляются в информационном блоке, а затем также отбрасывается проверочный блок.

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

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

Читайте также: