Каналы передачи данных ненадежны (шумы, наводки и т.д.), да и само оборудование обработки информации работает со сбоями. По этой причине важную роль приобретают механизмы детектирования ошибок. Ведь если ошибка обнаружена, можно осуществить повторную передачу данных и решить проблему. Если исходный код по своей длине равен полученному коду, обнаружить ошибку передачи не предоставляется возможным. Можно, конечно, передать код дважды и сравнить, но это уже двойная избыточность.
Простейшим способом обнаружения ошибок является контроль по М бит). Этому блоку ставится в соответствие кодовое слово длиной N бит, причем N>M. Избыточность кода характеризуется величиной 1-M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность).
При передаче информации она кодируется таким образом, чтобы с одной стороны характеризовать ее минимальным числом символов, а с другой – минимизировать вероятность ошибки при декодировании получателем. Для выбора типа кодирования важную роль играет так называемое
Пусть А и Б — две двоичные кодовые последовательности равной длины. 00111 и 10101 равно 2.
Можно показать, что для детектирования ошибок в n битах схема кодирования требует применения кодовых слов с N + 1. Можно также показать, что для исправления ошибок в N битах необходима схема кодирования с 2N + 1. Таким образом, конструируя код, мы пытаемся обеспечить
Широко распространены коды с одиночным битом М бит добавляется 1 бит, значение которого определяется М бит. Так, например, для двухбитовых кодов 00, 01, 10, 11 кодами с контролем 000, 011, 101 и 110. Если в процессе передачи один бит будет передан неверно, М+1 бита изменится.
Предположим, что частота ошибок ( BER – Bit р = 10-4. В этом случае вероятность передачи 8 бит с ошибкой составит 1 – (1 – p)8 = 7,9 х 10-4. Добавление бита 9p(1 – p)8. Вероятность же реализации необнаруженной ошибки составит 1 – (1 – p)9 – 9p(1 – p)8 = 3,6 x 10-7. Таким образом, добавление бита
Контроль по
В Ethernet вычисление R(x) = 1 + x2 + x3 + x5 + x7. В этой схеме входной код приходит слева.
(рис 4.1) Схема реализации расчета CRC
Эффективность (1/2)r, где r — степень
x12 + x11 + x3 + x2 + x1 + 1 |
|
x16 + x15 + x2 + 1 |
|
x16 + x12 + x5 + 1 |
Исправлять ошибки труднее, чем их детектировать или предотвращать. Процедура коррекции ошибок предполагает два совмещеных процесса: обнаружение ошибки и определение места (идентификации сообщения и позиции в сообщении). После решения этих двух задач исправление тривиально — надо инвертировать значение ошибочного бита. В наземных каналах связи, где вероятность ошибки невелика, обычно используется метод детектирования ошибок и повторной пересылки фрагмента, содержащего дефект. Для спутниковых каналов с типичными для них большими задержками системы коррекции ошибок становятся привлекательными. Здесь используют
00000000
11110000
00001111
11111111
При получении кода 00000111 нетрудно предположить, что правильное значение полученного кода равно 00001111. Другие коды отстоят от полученного на большее
Рассмотрим пример передачи кода буквы s = 0x073 = 1110011 с использованием
| Позиция бита | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Значение бита | 1 | 1 | 1 | * | 0 | 0 | 1 | * | 1 | * | * |
Символами * помечены четыре позиции, где должны размещаться контрольные биты. Эти позиции определяются целой степенью 2 (1, 2, 4, 8 и т.д.). Контрольная сумма формируется путем выполнения операции XoR (исключающее ИЛИ) над кодами позиций ненулевых битов. В данном случае это 11, 10, 9, 5 и 3. Вычислим контрольную сумму:
| 11= | 1011 |
| 10= | 1010 |
| 09= | 1001 |
| 05= | 0101 |
| 03= | 0011 |
| $$\Sigma=$$ | 1110 |
Таким образом, приемник получит код
| Позиция бита | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Значение бита | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Просуммируем снова коды позиций ненулевых битов и получим нуль;
| 11= | 1011 |
| 10= | 1010 |
| 09= | 1001 |
| 08= | 1000 |
| 05= | 0101 |
| 04= | 0100 |
| 03= | 0011 |
| 02= | 0010 |
| $$\Sigma=$$ | 0000 |
Ну а теперь рассмотрим два случая ошибок в одном из битов посылки, например в бите 7 (1 вместо 0) и в бите 5 (0 вместо 1). Просуммируем коды позиций ненулевых битов еще раз:
|
|
В обоих случаях контрольная сумма равна позиции бита, переданного с ошибкой. Теперь для исправления ошибки достаточно инвертировать бит, номер которого указан в контрольной сумме. Понятно, что если ошибка произойдет при передаче более чем одного бита,
В общем случае код имеет N = M + C бит и предполагается, что не более чем один бит в коде может иметь ошибку. Тогда возможно N+1 состояние кода (правильное состояние и n ошибочных). Пусть М = 4, а N = 7, тогда слово-сообщение будет иметь вид: M4, M3, M2, C3, M1, C2, C1. Теперь попытаемся вычислить значения С1, С2, С3. Для этого используются уравнения, где все операции представляют собой сложение по модулю 2:
С1 = М1 + М2 + М4 С2 = М1 + М3 + М4 С3 = М2 + М3 + М4
Для определения того, доставлено ли сообщение без ошибок, вычисляем следующие выражения (сложение по модулю 2):
С11 = С1 + М4 + М2 + М1 С12 = С2 + М4 + М3 + М1 С13 = С3 + М4 + М3 + М2
Результат вычисления интерпретируется следующим образом:
| C11 | C12 | C13 | Значение |
|---|---|---|---|
| 1 | 2 | 4 | Позиция бит |
| 0 | 0 | 0 | Ошибок нет |
| 0 | 0 | 1 | Бит С3 неверен |
| 0 | 1 | 0 | Бит С2 неверен |
| 0 | 1 | 1 | Бит M3 неверен |
| 1 | 0 | 0 | Бит С1 неверен |
| 1 | 0 | 1 | Бит M2 неверен |
| 1 | 1 | 0 | Бит M1 неверен |
| 1 | 1 | 1 | Бит M4 неверен |
Описанная схема легко переносится на любое число n и М.
Число возможных кодовых комбинаций М n классов, где N — число разрешенных кодов. Разделение на классы осуществляется так, чтобы в каждый класс вошел один разрешенный код и ближайшие к нему (по qm.
В теории кодирования существуют следующие оценки максимального числа N n -разрядных кодов с расстоянием D.
d=1 |
n=2n |
d=2 |
n=2n-1 |
d=3 |
N 2n/(1 + n) |
d = 2q + 1 |
(для |
В случае k разрядов используются в качестве информационных, причем
K = n – log(n + 1), откуда следует (логарифм по основанию 2), что k может принимать значения 0, 1, 4, 11, 26, 57 и т.д., это и определяет соответствующие
Обобщением кодов Хэмминга являются
Одной из старейших схем коррекции ошибок является двух-и трехмерная позиционная схема (рис 4.2). Для каждого байта вычисляется бит Z, слои с 1 до N ). Если при транспортировке будет искажен один бит, он может быть найден и исправлен по неверным битам N+1.
Таким образом, на 512 передаваемых байтов данных пересылается около 200 бит
(рис 4.2) Позиционная схема коррекции ошибокКоды Рида-Соломона были предложены в 1960 году Ирвином Ридом (Irving S. Reed) и Густавом Соломоном (Gustave Solomon), являвшимися сотрудниками Линкольнской лаборатории МТИ. Ключом к использованию этой технологии стало изобретение эффективного алгоритма декодирования Элвином Беликамфом (Elwyn Berlekamp; http://en.wikipedia.org/wiki/Berlekamp-Massey_algorithm), профессором Калифорнийского университета (Беркли). Коды Рида-Соломона (см. также http://www.4i2i.com/reed_solomon_codes.htm) базируются на блочном принципе коррекции ошибок и используются в огромном числе приложений в сфере цифровых телекоммуникаций и при построении запоминающих устройств. Коды Рида-Соломона применяются для исправления ошибок во многих системах:
На рис 4.3 показаны практические приложения (дальние космические проекты) коррекции ошибок с использованием различных алгоритмов (Хэмминга, кодов свертки,
(рис 4.3) Несовершенство кода, как функция размера информационного блока для разных задач и алгоритмовТиповая система представлена ниже (см. http://www.4i2i.com/reed_solomon_codes.htm)
(рис 4.4) Схема коррекции ошибок Рида-СоломонаКодировщик Рида-Соломона берет блок цифровых данных и добавляет дополнительные "избыточные" биты. Ошибки происходят при передаче по каналам связи или по разным причинам при запоминании (например, из-за шума или наводок, царапин на CD и т.д.). Декодер Рида-Соломона обрабатывает каждый блок, пытается исправить ошибки и восстановить исходные данные. Число и типы ошибок, которые могут быть исправлены, зависят от характеристик кода Рида-Соломона.
Коды Рида-Соломона являются субнабором кодов RS(n,k) s -битных символов.
Это означает, что кодировщик воспринимает k информационных символов по s битов каждый и добавляет символы n символьного кодового слова. Имеется nk символов s битов каждый. Декодер Рида-Соломона может корректировать до t символов, которые содержат ошибки в кодовом слове, где 2t = n–k.
Диаграмма, представленная ниже, показывает типовое кодовое слово Рида-Соломона:
(рис 4.5) Структура кодового слова R-SПример. Популярным кодом Рида-Соломона является RS(255, 223) с 8-битными символами. Каждое кодовое слово содержит 255 байт, из которых 223 являются информационными и 32 байтами
n = 255, k = 223, s = 8
2t = 32, t = 16
Декодер может исправить любые 16 символов с ошибками в кодовом слове: то есть ошибки могут быть исправлены, если число искаженных байт не превышает 16.
При размере символа s, максимальная длина кодового слова ( n ) для кода Рида-Соломона равна n = 2s – 1.
Например, максимальная длина кода с 8-битными символами ( s = 8 ) равна 255 байтам.
Коды Рида-Соломона могут быть в принципе укорочены путем обнуления некоторого числа информационных символов на входе кодировщика (передавать их в этом случае не нужно). При передаче данных декодеру эти нули снова вводятся в массив.
Пример. Код (255, 223), описанный выше, может быть укорочен до (200, 168). Кодировщик будет работать с блоком данных 168 байт, добавит 55 нулевых байт, сформирует кодовое слово (255, 223) и передаст только 168 информационных байт и 32 байта
Объем вычислительной мощности, необходимой для кодирования и декодирования кодов Рида-Соломона, зависит от числа символов t означает, что большее число ошибок может быть исправлено, но это потребует большей вычислительной мощности по сравнению с вариантом при меньшем t.
Одна ошибка в символе происходит, когда 1 бит символа оказывается неверным или когда все биты неверны.
Пример. Код RS(255,223) может исправить до 16 ошибок в символах. В худшем случае, могут иметь место 16 битовых ошибок в разных символах (байтах). В лучшем случае, корректируются 16 полностью неверных байт, при этом исправляется 16 x 8 = 128 битовых ошибок.
Коды Рида-Соломона особенно хорошо подходят для корректировки кластеров ошибок (когда неверными оказываются большие группы бит кодового слова, следующие подряд).
Алгебраические процедуры декодирования Рида-Соломона могут исправлять ошибки и потери. Потерей считается случай, когда положение неверного символа известно. Декодер может исправить до t ошибок или до 2t потерь. Данные о потере (стирании) могут быть получены от демодулятора цифровой коммуникационной системы, т.е. демодулятор помечает полученные символы, которые вероятно содержат ошибки.
Когда кодовое слово декодируется, возможны три варианта.
2s + r < 2t ( s ошибок, r потерь), тогда исходное переданное кодовое слово всегда будет восстановлено. В противном случаеВероятность каждого из этих вариантов зависит от типа используемого кода Рида-Соломона, а также от числа и распределения ошибок.
Преимущество использования кодов Рида-Соломона заключается в том, что вероятность сохранения ошибок в декодированных данных обычно много меньше, чем вероятность ошибок, если коды Рида-Соломона не используются. Это часто называется выигрышем кодирования.
Пример. Пусть имеется цифровая телекоммуникационная система, работающая с
Кодирование и декодирование Рида-Соломона может быть выполнено аппаратно или программно.
Коды Рида-Соломона базируются на специальном разделе математики – полях Галуа (GF) или конечных полях. Арифметические действия (+,-, x, / и т.д.) над элементами конечного поля дают результат, который также является элементом этого поля. Кодировщик или декодер РидаСоломона должны уметь выполнять эти арифметические операции. Эти операции для своей реализации требуют специального оборудования или специализированного программного обеспечения.
Кодовое слово Рида-Соломона формируется с привлечением специального полинома. Все корректные кодовые слова должны делиться без остатка на эти
g(x) = (x – ai)(x – ai+1)...(x – ai+2t)
а кодовое слово формируется с помощью операции
c(x) = g(x).i(x)
где g(x) является i(x) представляет собой информационный блок, c(x) – кодовое слово, называемое простым элементом поля.
Пример. Генератор для RS(255, 249)
g(x)= (x – a0)(x – a1)(x – a2)(x – a3)(x – a4)(x – a5) g(x)= x6 + g5x5 + g3x3 + g2x2 + g1x1 + g0
2t символов
Ниже показана схема реализации кодировщика для версии RS(255,249):
(рис 4.6) Схема кодировщика R-SКаждый из 6 регистров содержит в себе символ (8 бит). Арифметические операторы выполняют сложение или умножение на символ как на элемент конечного поля.
Общая схема декодирования кодов Рида-Соломона показана ниже на рис 4.7.
(рис 4.7) Схема работы с кодами Рида-СоломонаОбозначения:
r(x) – Полученное кодовое словоSi – СиндромыL(x) – Полином локации ошибокXi – Положения ошибокYi – Значения ошибокc(x) – Восстановленное кодовое словоv – Число ошибокПолученное кодовое слово r(x) представляет собой исходное (переданное) кодовое слово c(x) плюс ошибки:
r(x) = c(x) + e(x)
Декодер Рида-Соломона пытается определить позицию и значение ошибки для t ошибок (или 2t потерь) и исправить ошибки и потери.
Вычисление синдрома похоже на вычисление 2t синдромов, это зависит только от ошибок (а не передаваемых кодовых слов). Синдромы могут быть вычислены путем подстановки 2t корней g(x) в r(x).
Это делается путем решения системы уравнений с t неизвестными. Существует несколько быстрых алгоритмов для решения этой задачи. Эти алгоритмы используют особенности структуры матрицы кодов РидаСоломона и сильно сокращают необходимую вычислительную мощность. Делается это в два этапа.
1. Определение полинома локации ошибок.
Это может быть сделано с помощью алгоритма Berlekamp-Massey или алгоритма Эвклида. Алгоритм Эвклида используется чаще на практике, так как его легче реализовать, однако алгоритм Berlekamp-Massey позволяет получить более эффективную реализацию оборудования и программ.
2. Нахождение корней этого полинома. Это делается с привлечением алгоритма поиска Chien.
Здесь также нужно решить систему уравнений с t неизвестными. Для решения используется быстрый алгоритм Forney.
Существует несколько коммерческих аппаратных реализаций. Имеется много разработанных интегральных схем, предназначенных для кодирования и декодирования кодов Рида-Соломона. Эти ИС допускают определенный уровень программирования (например RS(255, k), где t может принимать значения от 1 до 16).
До недавнего времени программные реализации в "реальном времени" требовали слишком большой вычислительной мощности практически для всех кодов Рида-Соломона. Главной трудностью в программной реализации кодов Рида-Соломона являлось то, что процессоры общего назначения не поддерживают арифметические операции для поля Галуа. Однако оптимальное составление программ в сочетании с возросшей вычислительной мощностью позволяют получить вполне приемлемые результаты для относительно высоких скоростей передачи данных.
Транспортировка данных подвержена влиянию шумов и наводок, которые вносят искажения. Если вероятность повреждения данных мала, достаточно зарегистрировать сам факт искажения и повторить передачу поврежденного фрагмента.
Когда вероятность искажения велика, например, в каналах коммуникаций с геостационарными спутниками, используются методы коррекции ошибок.
Блочное кодирование работает с блоками (пакетами) бит или символов фиксированного размера. Метод свертки работает с потоками бит или символов произвольной протяженности. Коды свертки при желании могут быть преобразованы в блочные коды.
Существует большое число блочных кодов, одним из наиболее важных является
Для
В 1967 году Эндрю Витерби (Andrew Viterbi) разработал технику декодирования, которая стала стандартной для кодов свертки. Эта методика требовала меньше памяти. Метод свертки более эффективен, когда ошибки распределены случайным образом, а не группируются в кластеры. Работа же с кластерами ошибок более эффективна при использовании алгебраического кодирования.
Одной из широко применяемых разновидностей коррекции ошибок является турбо-кодирование, разработанное американской аэрокосмической корпорацией. В этой схеме комбинируется два или более относительно простых кодов свертки. В k бит снабжаются кодами
В результате через канал передается n -битовое кодовое слово ( n>k ). Конкретная реализация алгоритма n, k ). Применение
В 1974 году Йозеф Оденвальдер (Joseph odenwalder) объединил возможности алгебраического кодирования и метода свертки. Хорошего результата можно добиться, введя специальную операцию псевдослучайного перемешивания бит (interleaver).
В 1993 году группой Клода Берроу (Claude Berrou) был разработан турбо-код. В кодеке, реализующем этот алгоритм, содержатся кодировщики как минимум двух компонент (реализующие алгебраический метод или свертку). Кодирование осуществляется для блоков данных. Здесь также используется псевдослучайное перемешивание бит перед передачей. Это приводит к тому, что кластеры ошибок, внесенных при транспортировке, оказываются разнесенными случайным образом в пределах блока данных.
На рис 4.8 проводится сравнение вариантов S/N ). Из этих данных видно, что при отношении S/N= 8 дБ применение
За последние пять лет были разработаны программы, которые позволяют оптимизировать структуры турбо-кодов. Улучшение S/N уже не дает никакого выигрыша. Но схемы, позволяющие смягчить влияние этого насыщения, продолжают разрабатываться.
(рис 4.8) Турбо-кодек должен иметь столько же компонентных декодеров, сколько имеется кодировщиков на стороне передатчика. Декодеры соединяются последовательно.
(рис 4.9) Турбо-декодерТехника
Следует помнить, что, как в случае
Каналы передачи данных ненадежны (шумы, наводки и т.д.), да и само оборудование обработки информации работает со сбоями. По этой причине важную роль приобретают механизмы детектирования ошибок. Ведь если ошибка обнаружена, можно осуществить повторную передачу данных и решить проблему. Если исходный код по своей длине равен полученному коду, обнаружить ошибку передачи не предоставляется возможным. Можно, конечно, передать код дважды и сравнить, но это уже двойная избыточность.
Простейшим способом обнаружения ошибок является контроль по М бит). Этому блоку ставится в соответствие кодовое слово длиной N бит, причем N>M. Избыточность кода характеризуется величиной 1-M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность).
При передаче информации она кодируется таким образом, чтобы с одной стороны характеризовать ее минимальным числом символов, а с другой – минимизировать вероятность ошибки при декодировании получателем. Для выбора типа кодирования важную роль играет так называемое
Пусть А и Б — две двоичные кодовые последовательности равной длины. 00111 и 10101 равно 2.
Можно показать, что для детектирования ошибок в n битах схема кодирования требует применения кодовых слов с N + 1. Можно также показать, что для исправления ошибок в N битах необходима схема кодирования с 2N + 1. Таким образом, конструируя код, мы пытаемся обеспечить
Широко распространены коды с одиночным битом М бит добавляется 1 бит, значение которого определяется М бит. Так, например, для двухбитовых кодов 00, 01, 10, 11 кодами с контролем 000, 011, 101 и 110. Если в процессе передачи один бит будет передан неверно, М+1 бита изменится.
Предположим, что частота ошибок ( BER – Bit р = 10-4. В этом случае вероятность передачи 8 бит с ошибкой составит 1 – (1 – p)8 = 7,9 х 10-4. Добавление бита 9p(1 – p)8. Вероятность же реализации необнаруженной ошибки составит 1 – (1 – p)9 – 9p(1 – p)8 = 3,6 x 10-7. Таким образом, добавление бита
Контроль по
В Ethernet вычисление R(x) = 1 + x2 + x3 + x5 + x7. В этой схеме входной код приходит слева.
(рис 4.1) Схема реализации расчета CRC
Эффективность (1/2)r, где r — степень
x12 + x11 + x3 + x2 + x1 + 1 |
|
x16 + x15 + x2 + 1 |
|
x16 + x12 + x5 + 1 |
Исправлять ошибки труднее, чем их детектировать или предотвращать. Процедура коррекции ошибок предполагает два совмещеных процесса: обнаружение ошибки и определение места (идентификации сообщения и позиции в сообщении). После решения этих двух задач исправление тривиально — надо инвертировать значение ошибочного бита. В наземных каналах связи, где вероятность ошибки невелика, обычно используется метод детектирования ошибок и повторной пересылки фрагмента, содержащего дефект. Для спутниковых каналов с типичными для них большими задержками системы коррекции ошибок становятся привлекательными. Здесь используют
00000000
11110000
00001111
11111111
При получении кода 00000111 нетрудно предположить, что правильное значение полученного кода равно 00001111. Другие коды отстоят от полученного на большее
Рассмотрим пример передачи кода буквы s = 0x073 = 1110011 с использованием
| Позиция бита | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Значение бита | 1 | 1 | 1 | * | 0 | 0 | 1 | * | 1 | * | * |
Символами * помечены четыре позиции, где должны размещаться контрольные биты. Эти позиции определяются целой степенью 2 (1, 2, 4, 8 и т.д.). Контрольная сумма формируется путем выполнения операции XoR (исключающее ИЛИ) над кодами позиций ненулевых битов. В данном случае это 11, 10, 9, 5 и 3. Вычислим контрольную сумму:
| 11= | 1011 |
| 10= | 1010 |
| 09= | 1001 |
| 05= | 0101 |
| 03= | 0011 |
| $$\Sigma=$$ | 1110 |
Таким образом, приемник получит код
| Позиция бита | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Значение бита | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Просуммируем снова коды позиций ненулевых битов и получим нуль;
| 11= | 1011 |
| 10= | 1010 |
| 09= | 1001 |
| 08= | 1000 |
| 05= | 0101 |
| 04= | 0100 |
| 03= | 0011 |
| 02= | 0010 |
| $$\Sigma=$$ | 0000 |
Ну а теперь рассмотрим два случая ошибок в одном из битов посылки, например в бите 7 (1 вместо 0) и в бите 5 (0 вместо 1). Просуммируем коды позиций ненулевых битов еще раз:
|
|
В обоих случаях контрольная сумма равна позиции бита, переданного с ошибкой. Теперь для исправления ошибки достаточно инвертировать бит, номер которого указан в контрольной сумме. Понятно, что если ошибка произойдет при передаче более чем одного бита,
В общем случае код имеет N = M + C бит и предполагается, что не более чем один бит в коде может иметь ошибку. Тогда возможно N+1 состояние кода (правильное состояние и n ошибочных). Пусть М = 4, а N = 7, тогда слово-сообщение будет иметь вид: M4, M3, M2, C3, M1, C2, C1. Теперь попытаемся вычислить значения С1, С2, С3. Для этого используются уравнения, где все операции представляют собой сложение по модулю 2:
С1 = М1 + М2 + М4 С2 = М1 + М3 + М4 С3 = М2 + М3 + М4
Для определения того, доставлено ли сообщение без ошибок, вычисляем следующие выражения (сложение по модулю 2):
С11 = С1 + М4 + М2 + М1 С12 = С2 + М4 + М3 + М1 С13 = С3 + М4 + М3 + М2
Результат вычисления интерпретируется следующим образом:
| C11 | C12 | C13 | Значение |
|---|---|---|---|
| 1 | 2 | 4 | Позиция бит |
| 0 | 0 | 0 | Ошибок нет |
| 0 | 0 | 1 | Бит С3 неверен |
| 0 | 1 | 0 | Бит С2 неверен |
| 0 | 1 | 1 | Бит M3 неверен |
| 1 | 0 | 0 | Бит С1 неверен |
| 1 | 0 | 1 | Бит M2 неверен |
| 1 | 1 | 0 | Бит M1 неверен |
| 1 | 1 | 1 | Бит M4 неверен |
Описанная схема легко переносится на любое число n и М.
Число возможных кодовых комбинаций М n классов, где N — число разрешенных кодов. Разделение на классы осуществляется так, чтобы в каждый класс вошел один разрешенный код и ближайшие к нему (по qm.
В теории кодирования существуют следующие оценки максимального числа N n -разрядных кодов с расстоянием D.
d=1 |
n=2n |
d=2 |
n=2n-1 |
d=3 |
N 2n/(1 + n) |
d = 2q + 1 |
(для |
В случае k разрядов используются в качестве информационных, причем
K = n – log(n + 1), откуда следует (логарифм по основанию 2), что k может принимать значения 0, 1, 4, 11, 26, 57 и т.д., это и определяет соответствующие
Обобщением кодов Хэмминга являются
Одной из старейших схем коррекции ошибок является двух-и трехмерная позиционная схема (рис 4.2). Для каждого байта вычисляется бит Z, слои с 1 до N ). Если при транспортировке будет искажен один бит, он может быть найден и исправлен по неверным битам N+1.
Таким образом, на 512 передаваемых байтов данных пересылается около 200 бит
(рис 4.2) Позиционная схема коррекции ошибокКоды Рида-Соломона были предложены в 1960 году Ирвином Ридом (Irving S. Reed) и Густавом Соломоном (Gustave Solomon), являвшимися сотрудниками Линкольнской лаборатории МТИ. Ключом к использованию этой технологии стало изобретение эффективного алгоритма декодирования Элвином Беликамфом (Elwyn Berlekamp; http://en.wikipedia.org/wiki/Berlekamp-Massey_algorithm), профессором Калифорнийского университета (Беркли). Коды Рида-Соломона (см. также http://www.4i2i.com/reed_solomon_codes.htm) базируются на блочном принципе коррекции ошибок и используются в огромном числе приложений в сфере цифровых телекоммуникаций и при построении запоминающих устройств. Коды Рида-Соломона применяются для исправления ошибок во многих системах:
На рис 4.3 показаны практические приложения (дальние космические проекты) коррекции ошибок с использованием различных алгоритмов (Хэмминга, кодов свертки,
(рис 4.3) Несовершенство кода, как функция размера информационного блока для разных задач и алгоритмовТиповая система представлена ниже (см. http://www.4i2i.com/reed_solomon_codes.htm)
(рис 4.4) Схема коррекции ошибок Рида-СоломонаКодировщик Рида-Соломона берет блок цифровых данных и добавляет дополнительные "избыточные" биты. Ошибки происходят при передаче по каналам связи или по разным причинам при запоминании (например, из-за шума или наводок, царапин на CD и т.д.). Декодер Рида-Соломона обрабатывает каждый блок, пытается исправить ошибки и восстановить исходные данные. Число и типы ошибок, которые могут быть исправлены, зависят от характеристик кода Рида-Соломона.
Коды Рида-Соломона являются субнабором кодов RS(n,k) s -битных символов.
Это означает, что кодировщик воспринимает k информационных символов по s битов каждый и добавляет символы n символьного кодового слова. Имеется nk символов s битов каждый. Декодер Рида-Соломона может корректировать до t символов, которые содержат ошибки в кодовом слове, где 2t = n–k.
Диаграмма, представленная ниже, показывает типовое кодовое слово Рида-Соломона:
(рис 4.5) Структура кодового слова R-SПример. Популярным кодом Рида-Соломона является RS(255, 223) с 8-битными символами. Каждое кодовое слово содержит 255 байт, из которых 223 являются информационными и 32 байтами
n = 255, k = 223, s = 8
2t = 32, t = 16
Декодер может исправить любые 16 символов с ошибками в кодовом слове: то есть ошибки могут быть исправлены, если число искаженных байт не превышает 16.
При размере символа s, максимальная длина кодового слова ( n ) для кода Рида-Соломона равна n = 2s – 1.
Например, максимальная длина кода с 8-битными символами ( s = 8 ) равна 255 байтам.
Коды Рида-Соломона могут быть в принципе укорочены путем обнуления некоторого числа информационных символов на входе кодировщика (передавать их в этом случае не нужно). При передаче данных декодеру эти нули снова вводятся в массив.
Пример. Код (255, 223), описанный выше, может быть укорочен до (200, 168). Кодировщик будет работать с блоком данных 168 байт, добавит 55 нулевых байт, сформирует кодовое слово (255, 223) и передаст только 168 информационных байт и 32 байта
Объем вычислительной мощности, необходимой для кодирования и декодирования кодов Рида-Соломона, зависит от числа символов t означает, что большее число ошибок может быть исправлено, но это потребует большей вычислительной мощности по сравнению с вариантом при меньшем t.
Одна ошибка в символе происходит, когда 1 бит символа оказывается неверным или когда все биты неверны.
Пример. Код RS(255,223) может исправить до 16 ошибок в символах. В худшем случае, могут иметь место 16 битовых ошибок в разных символах (байтах). В лучшем случае, корректируются 16 полностью неверных байт, при этом исправляется 16 x 8 = 128 битовых ошибок.
Коды Рида-Соломона особенно хорошо подходят для корректировки кластеров ошибок (когда неверными оказываются большие группы бит кодового слова, следующие подряд).
Алгебраические процедуры декодирования Рида-Соломона могут исправлять ошибки и потери. Потерей считается случай, когда положение неверного символа известно. Декодер может исправить до t ошибок или до 2t потерь. Данные о потере (стирании) могут быть получены от демодулятора цифровой коммуникационной системы, т.е. демодулятор помечает полученные символы, которые вероятно содержат ошибки.
Когда кодовое слово декодируется, возможны три варианта.
2s + r < 2t ( s ошибок, r потерь), тогда исходное переданное кодовое слово всегда будет восстановлено. В противном случаеВероятность каждого из этих вариантов зависит от типа используемого кода Рида-Соломона, а также от числа и распределения ошибок.
Преимущество использования кодов Рида-Соломона заключается в том, что вероятность сохранения ошибок в декодированных данных обычно много меньше, чем вероятность ошибок, если коды Рида-Соломона не используются. Это часто называется выигрышем кодирования.
Пример. Пусть имеется цифровая телекоммуникационная система, работающая с
Кодирование и декодирование Рида-Соломона может быть выполнено аппаратно или программно.
Коды Рида-Соломона базируются на специальном разделе математики – полях Галуа (GF) или конечных полях. Арифметические действия (+,-, x, / и т.д.) над элементами конечного поля дают результат, который также является элементом этого поля. Кодировщик или декодер РидаСоломона должны уметь выполнять эти арифметические операции. Эти операции для своей реализации требуют специального оборудования или специализированного программного обеспечения.
Кодовое слово Рида-Соломона формируется с привлечением специального полинома. Все корректные кодовые слова должны делиться без остатка на эти
g(x) = (x – ai)(x – ai+1)...(x – ai+2t)
а кодовое слово формируется с помощью операции
c(x) = g(x).i(x)
где g(x) является i(x) представляет собой информационный блок, c(x) – кодовое слово, называемое простым элементом поля.
Пример. Генератор для RS(255, 249)
g(x)= (x – a0)(x – a1)(x – a2)(x – a3)(x – a4)(x – a5) g(x)= x6 + g5x5 + g3x3 + g2x2 + g1x1 + g0
2t символов
Ниже показана схема реализации кодировщика для версии RS(255,249):
(рис 4.6) Схема кодировщика R-SКаждый из 6 регистров содержит в себе символ (8 бит). Арифметические операторы выполняют сложение или умножение на символ как на элемент конечного поля.
Общая схема декодирования кодов Рида-Соломона показана ниже на рис 4.7.
(рис 4.7) Схема работы с кодами Рида-СоломонаОбозначения:
r(x) – Полученное кодовое словоSi – СиндромыL(x) – Полином локации ошибокXi – Положения ошибокYi – Значения ошибокc(x) – Восстановленное кодовое словоv – Число ошибокПолученное кодовое слово r(x) представляет собой исходное (переданное) кодовое слово c(x) плюс ошибки:
r(x) = c(x) + e(x)
Декодер Рида-Соломона пытается определить позицию и значение ошибки для t ошибок (или 2t потерь) и исправить ошибки и потери.
Вычисление синдрома похоже на вычисление 2t синдромов, это зависит только от ошибок (а не передаваемых кодовых слов). Синдромы могут быть вычислены путем подстановки 2t корней g(x) в r(x).
Это делается путем решения системы уравнений с t неизвестными. Существует несколько быстрых алгоритмов для решения этой задачи. Эти алгоритмы используют особенности структуры матрицы кодов РидаСоломона и сильно сокращают необходимую вычислительную мощность. Делается это в два этапа.
1. Определение полинома локации ошибок.
Это может быть сделано с помощью алгоритма Berlekamp-Massey или алгоритма Эвклида. Алгоритм Эвклида используется чаще на практике, так как его легче реализовать, однако алгоритм Berlekamp-Massey позволяет получить более эффективную реализацию оборудования и программ.
2. Нахождение корней этого полинома. Это делается с привлечением алгоритма поиска Chien.
Здесь также нужно решить систему уравнений с t неизвестными. Для решения используется быстрый алгоритм Forney.
Существует несколько коммерческих аппаратных реализаций. Имеется много разработанных интегральных схем, предназначенных для кодирования и декодирования кодов Рида-Соломона. Эти ИС допускают определенный уровень программирования (например RS(255, k), где t может принимать значения от 1 до 16).
До недавнего времени программные реализации в "реальном времени" требовали слишком большой вычислительной мощности практически для всех кодов Рида-Соломона. Главной трудностью в программной реализации кодов Рида-Соломона являлось то, что процессоры общего назначения не поддерживают арифметические операции для поля Галуа. Однако оптимальное составление программ в сочетании с возросшей вычислительной мощностью позволяют получить вполне приемлемые результаты для относительно высоких скоростей передачи данных.
Транспортировка данных подвержена влиянию шумов и наводок, которые вносят искажения. Если вероятность повреждения данных мала, достаточно зарегистрировать сам факт искажения и повторить передачу поврежденного фрагмента.
Когда вероятность искажения велика, например, в каналах коммуникаций с геостационарными спутниками, используются методы коррекции ошибок.
Блочное кодирование работает с блоками (пакетами) бит или символов фиксированного размера. Метод свертки работает с потоками бит или символов произвольной протяженности. Коды свертки при желании могут быть преобразованы в блочные коды.
Существует большое число блочных кодов, одним из наиболее важных является
Для
В 1967 году Эндрю Витерби (Andrew Viterbi) разработал технику декодирования, которая стала стандартной для кодов свертки. Эта методика требовала меньше памяти. Метод свертки более эффективен, когда ошибки распределены случайным образом, а не группируются в кластеры. Работа же с кластерами ошибок более эффективна при использовании алгебраического кодирования.
Одной из широко применяемых разновидностей коррекции ошибок является турбо-кодирование, разработанное американской аэрокосмической корпорацией. В этой схеме комбинируется два или более относительно простых кодов свертки. В k бит снабжаются кодами
В результате через канал передается n -битовое кодовое слово ( n>k ). Конкретная реализация алгоритма n, k ). Применение
В 1974 году Йозеф Оденвальдер (Joseph odenwalder) объединил возможности алгебраического кодирования и метода свертки. Хорошего результата можно добиться, введя специальную операцию псевдослучайного перемешивания бит (interleaver).
В 1993 году группой Клода Берроу (Claude Berrou) был разработан турбо-код. В кодеке, реализующем этот алгоритм, содержатся кодировщики как минимум двух компонент (реализующие алгебраический метод или свертку). Кодирование осуществляется для блоков данных. Здесь также используется псевдослучайное перемешивание бит перед передачей. Это приводит к тому, что кластеры ошибок, внесенных при транспортировке, оказываются разнесенными случайным образом в пределах блока данных.
На рис 4.8 проводится сравнение вариантов S/N ). Из этих данных видно, что при отношении S/N= 8 дБ применение
За последние пять лет были разработаны программы, которые позволяют оптимизировать структуры турбо-кодов. Улучшение S/N уже не дает никакого выигрыша. Но схемы, позволяющие смягчить влияние этого насыщения, продолжают разрабатываться.
(рис 4.8) Турбо-кодек должен иметь столько же компонентных декодеров, сколько имеется кодировщиков на стороне передатчика. Декодеры соединяются последовательно.
(рис 4.9) Турбо-декодерТехника
Следует помнить, что, как в случае
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.