Цифровая передача и управление ошибками

Методы обнаружения и коррекции ошибок в цифровых звуковых сигналах

В цифровых каналах
связи средняя вероятность появления
ошибки составляет 10^–5…10^–6,
а в отдельных случаях и 10^–4,
поэтому влияние ошибок на качество
звукопередачи неизбежно. Это вызывает
необходимость применения помехоустойчивого
кодирования при передаче сигналов ЗВ.

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

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

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

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

(1.37)

где
,
— число сочетаний изт
символов по
q.
Для
10-раз-рядных кодовых слов вероятность
появления двойных ошибок при исходной
вероятности р_ош = 10^–5
составляет p₁ = 510^–9,
а при р_ош = 10^–4
уже составляет р₂ = 510^–7.
Это соответствует появлению одной
двойной ошибки каждые 2,5…3 мин.

Кроме того, в
цифровых каналах передачи при средней
вероятности появления ошибки р_ош = 10^–4
и выше возникают коррелированные ошибки,
вызванные действием импульсных помех,
несовершенством систем коммутации и
т.д. Поэтому вероятность появления
ошибок большой кратности возрастает.
Особенно велика роль пакетов ошибок в
каналах цифровой магнитной записи и в
системе компакт-диска из-за возможных
повреждений носителя записи. Системы
исправления ошибок должны эффективно
бороться не только с одиночными, но и с
пакетами ошибок, заметность которых
существенно выше. Чем больше кратность
ошибки, тем больше должна быть избыточность,
которую необходимо вносить в сигнал.
Требуемая избыточность тем больше, чем
большее число разрядов кодовой группы
необходимо защищать. С учетом заметности
искажений в системах цифровой передачи
и записи ЗС обычно защищают от ошибок
пять-шесть старших разрядов информационных
символов кодируемых отсчетов, служебные
комбинации, определяющие, например,
номер шкалы квантования при почти
мгновенном компандировании. Ошибки в
младших разрядах, если частота их
появления не слишком велика, достаточно
обнаруживать и затем маскировать,
используя методы интерполяции, о которых
будет сказано ниже.

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

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

1. <—-> 0 0 0 0 0…0,

2. <—-> 1 1 1 1 1…1.

Это (n,1)-код.
Для него минимальное расстояние равно
n,
и в предположении, что большинство
принятых битов совпадает с переданным
информационным битом, может быть
исправлено (n–1)/2
ошибок. Если символы передать только
дважды, а затем обнаружить, что они
различаются, то нет возможности принять
решение о том, какое из двух чисел
является правильным. Каждое число нужно
передать по крайней мере трижды и после
сравнения распознать ошибочное. Такой
метод неэффективен, он приводит к резкому
увеличению требуемой скорости передачи.
Найдены другие, более эффективные
возможности.

Очень простыми
являются коды
с проверкой на четность. К
информационным битам каждого кодового
слова k-й
разрядности
добавляют (к+1)-й
бит так, чтобы полное число единиц (или
нулей) в кодовом слове было четным.
Данный прием в цифровых устройствах
из-за простоты используют очень часто.
При этом дополнительный бит называется
битом проверки
на четность (паритетным
битом). Например, для k = 4
имеем

и т.д.

Этот код является
(k
+ 1,k)-кодом.
Минимальное расстояние кода равно 2, и,
следовательно, ошибки могут быть
обнаружены, но никакие ошибки не могут
быть исправлены. Если бит передается
неправильно, то распознается появление
ошибки в слове (ибо сумма всех единиц
не будет равна четному числу, если ошибка
одиночная). Однако позицию ошибки в
кодовой комбинации определить невозможно.
Таким образом, данный код не позволяет
исправить ошибки. В силу этого данный
код используется только для обнаружения
одиночных ошибок, но не для их исправления.

Впрочем, можно
распознать позицию единичных (отдельных)
ошибок, если несколько слов предварительно
объединить в матрицу, а контрольные
разряды четности (дополнительные биты
проверки на четность) добавить к
информационным символам кодовых слов
построчно и по столбцам, например:

Правильно
Ошибка в первой строке, третий столбец

(выделена
подчеркиванием)

(неправильная
четность)

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

Маскирование
ошибок. Если
средняя вероятность появления ошибки
не превышает р_ош = 10^–5
и источником ошибок является шум в
канале передачи, то расчеты показывают,
что одиночные ошибки появляются в
среднем 2 раза в секунду, а двойные —
примерно 4 раза в сутки. В этих условиях
достаточно учитывать только одиночные
ошибки. Действие последних приводит к
искажению величины отдельных отсчетов
сигнала, и эффективным способом борьбы
с ними является обнаружение ошибочно
принятых кодовых слов с последующим
маскированием искаженных отсчетов. Для
обнаружения обычно используется уже
описанный выше принцип проверки на
четность, причем такой, чтобы число
единиц в кодовом слове было четным. При
приеме после выделения кодовых слов в
каждом из них подсчитывается число
единиц. Нечетное их число будет означать
наличие ошибки в данном кодовом слове.

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

,
(1.38)

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

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

Рис. 1.21
— Маскирование ошибочных отсчетов:

а
— обнаруженная ошибка в значении отсчета
s_n;
б — замена
ошибочного отсчета s_n
отсчетом с
нулевым значением; в
— коррекция (экстраполяция нулевого
порядка) через замену ошибочного отсчета
s_n
его предыдущим значением s_n–1;
г — интерполяция
первого порядка путем вычисления
среднего значения из предыдущего s_n–1
и последующего s_n+1
отсчетов

Поскольку слух
человека инерционен, то метод маскирования
оказывается эффективным, если число
ошибок не превышает одной-двух в секунду.
Это условие выполняется при вероятности
появления ошибки в канале р_ош = 10^–5.
При т = 6
в этом случае получаем, что вероятность
необнаруженной ошибки р₀ = 1510^–10,
что примерно соответствует требуемому
значению.

Увеличение р_ош
до значения
10^–4
ведет к резкому росту среднего числа
ошибок в секунду до 20. Метод интерполяции
первого порядка не обеспечивает полного
маскирования ошибок полезным сигналом,
они становятся уже заметными на слух.
Можно считать, что изложенный выше метод
маскирования применим, когда значение
р_от

10^–5.

Исправление
ошибок. Если
вероятность ошибки превышает р_ош = 10^–5,
то образуются пакеты ошибок и от их
маскирования приходится переходить к
исправлению. Для исправления ошибок
применяют помехоустойчивое кодирование.
При этом наиболее широкое распространение
получили блочные линейные (m,k)-ко-ды.
У таких кодов передаваемая последовательность
символов разделена на блоки, содержащие
одинаковое число символов. Общее число
символов (битов) в кодовом слове равно
m,
из них информационными являются первые
k
символов, а последние r = т – k
символов —
проверочными. Проверочные символы
формируются в результате выполнения
некоторых линейных операций над
информационными символами. В частности,
проверочные символы могут являться
суммой по модулю 2 различных сочетаний
информационных символов. Чем больше
число проверочных символов, тем больше
корректирующие возможности кода.
Особенностью линейного кода является
также то, что сумма (и разность) входящих
в код кодовых слов также является кодовым
словом, принадлежащим этому коду.

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

(1.39)

где R
— избыточность
кода.

Наиболее известной
разновидностью блочных линейных (т,
k)-кодов
являются коды Хэмминга. Для каждого т
существует
(2^m–1,
2^m–1 – m)-код
Хэмминга. Кроме параметров т
и k,
важным
является минимальное расстояние d,
определяющее
меру различия двух наиболее похожих
кодовых слов. Расстоянием d
по Хэммингу
между двумя q-ичными
последовательностями х
и у
длины n
называется число позиций, в которых они
различны. Это расстояние обозначается
d(x,y).
Например,
если х = 10101
и у = 01100,
то имеем d(10101,
01100) = 3. При этом минимальное
расстояние кода равно наименьшему
значению из всех расстояний по Хэммингу
между различными парами кодовых слов
в коде; (п,
k)-код
с минимальным расстоянием d
называется
также (п,
k,
d)—кoдoм.

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

(1.40)

Например, для
обнаружения одиночной ошибки d = 2.
Это означает, что достаточно информационные
кодовые группы увеличить на один разряд.
Для исправления одиночных ошибок каждую
кодовую группу необходимо увеличить
уже на три разряда. С ростом кратности
ошибок объем требуемой дополнительной
информации резко возрастает. Так, для
числа k
битов
аудиоданных требуется следующее число
контрольных (дополнительных, проверочных)
битов r
в коде Хэмминга, чтобы ошибка могла быть
исправлена:

Контрольные биты
рассчитываются (вычисляются) путем
сложений по модулю 2. В них участвуют
информационные биты аудиоданных по
меньшей мере дважды. Чтобы с большой
вероятностью обнаружить ошибку в потоке
данных, информационные слова и контрольные
слова охватываются совместно в блоки.
Эти блоки затем снова рассматриваются
как отдельные единицы информации и
далее кодируются (блочный код). Иногда
удается исправлять конфигурацию из t
ошибок даже
в том случае, если неравенство (1.40)
не выполняется. Однако если d
< (2t
+ 1), то
исправление любых t
ошибок не
может быть гарантировано, так как оно
зависит от передаваемого слова и
конфигурации из t
ошибок,
возникших внутри блока.

При кодовом
расстоянии d = 3
коды Хэмминга имеют длину т = 2^r–1.
При двух проверочных символах r = 2
существует код Хэмминга (3,1); при r = 3
— код (7,4); при r = 4
— код (15,11)
и т.д. Коды, для которых d = 3,
могут исправлять одиночную ошибку. Для
нахождения места этой ошибки необходимо
выполнить r
проверок, представляющих собой операции
суммирования по модулю 2. Технически
это реализуется достаточно просто.
Например, (7,4)-код Хэмминга можно описать
с помощью реализации, приведенной на
рис. 1.22,
а.

Рис. 1.22
— Кодек для простого (7,4)-кода Хэмминга:

а — кодер;
б — декодер

При заданных
четырех информационных битах данных
(i₁,
i₂,
i₃,
i₄)
каждое кодовое слово дополняется тремя
проверочными битами, задаваемыми
равенствами

(1.42)

Знак «+» здесь
означает сложение по модулю 2: 0 + 0 = 0,
0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0. Шестнадцать
разрешенных кодовых слов (7,4)-кода
Хэмминга имеют вид (i₁,i₂,
i₃,
i₄,
r₁,
r₂,
r₃):

Пусть при передаче
в принятом слове v = (i‘₁,
i‘₂,
i‘₃,
i‘₄,
r‘₁,
r‘₂,
r‘₃).
По изображенному
на рис. 1.22,
б коду
вычисляются биты

(1.44)

Трехбитовая
последовательность (s₁,
s₂,
s₃)
называется
синдромом.
Она зависит
только от конфигурации ошибок. Всего
имеется восемь возможных синдромов:
один для случая отсутствия ошибки и по
одному для каждой из семи возможных
одиночных ошибок, при этом каждая ошибка
имеет только свой единственный синдром.
Несложно сконструировать цифровую
логику, которая по синдрому локализует
соответствующий ошибочный бит. После
исправления ошибки проверочные символы
опускаются. При наличии двух и более
ошибок код будет ошибаться: он предназначен
для исправления только одной одиночной
ошибки в кодовом слове группы.

При d = 4
коды Хэмминга имеют длину т = 2^r–1
и записываются
соответственно как (4,1); (8,4); (16,11) и т.д.
Они получаются из кодов Хэмминга с
минимальным расстоянием d = 3
добавлением к каждому кодовому слову
[см. (1.43)]
одного проверочного символа, равного
сумме по модулю 2 всех остальных символов,
как информационных, так и проверочных
для каждого кодового слова исходного
(7,4)-кода Хэмминга.

При выборе кода
важно определить мощность кода М,
т.е. максимальное
число кодовых слов в двоичном коде
длиной т
(множество
двоичных слов длины m)
при заданном кодовом расстоянии d.
Обычно при
d = 3

(1.45)

Следовательно,
(3, 1)-код Хэмминга состоит всего лишь из
двух кодовых слов. Для увеличения числа
кодовых слов необходимо увеличить длину
кодового слова: для (7,4)-кода Хэмминга
уже имеется 16 кодовых слов. С увеличением
m
растет сложность декодирования. Коды
Хэмминга в силу этой причины целесообразно
использовать для исправления одиночных
независимых ошибок при небольшом числе
возможных информационных символов. В
частности, коды Хэмминга используют
для передачи трехсимвольных комбинаций,
определяющих номер шкалы квантования
при кодировании ЗС с применением почти
мгновенного компандирования.

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

Кодовое слово
Z – (a₀,
a₁,
a₂,…,
a_n–1),
состоящее из n
символов, определяется полиномом
Y(x) = a₀
+ a₁x
+ a₂x²
+…+ a_n–1x^n–1.
Среди всех полиномов, соответствующих
кодовым словам циклического кода,
имеется ненулевой полином наименьшей
степени. Он называется порождающим,
степень его
r = n – k
(k
— число
информационных символов, n
— число символов в кодовом слове), а
свободный член равен единице. Основная
особенность порождающего полинома
заключается в том, что он полностью
определяет циклический код (все кодовые
слова циклического кода) и является
делителем всех полиномов, соответствующих
кодовым словам циклического кода.

Процесс кодирования
при использовании циклического кода
состоит в следующем. Полином G(x)
степени
(k – 1),
характеризующий k-разрядное
передаваемое информационное кодовое
слово, умножается на х^r.
Полученный
полином G(x)x^r
степени
k+r–1
делится на
порождающий полином F(x).
В результате
деления образуется остаток q(x)
степени не
более r – 1.
Полином Q(x) =
= x^rG(x)
+ q(x),
делящийся
на F(x)
без остатка,
определяет каждое разрешенное кодовое
слово циклического кода. Члены полинома
Q(x)
со степенью
r+1
и выше соответствуют информационным
символам, смещенным на r
разрядов в
результате операции умножения, а остаток
q(x)
от деления
— поверочным символам. Для обнаружения
или исправления ошибок в циклическом
коде обычно используют операцию деления
полинома Q₁(x)
принятого
кодового слова на заранее известный
порождающий полином F(x).
Если остаток
от деления не равен нулю, то принятое
кодовое слово считается ошибочным.
Место ошибки определяется детектором
ошибки в результате сравнения остатка
от деления с эталонным полиномом,
хранящимся в памяти. Биты избыточности,
полученные изложенным выше способом,
передаются совместно с первоначальными
битами данных.

Пример.
Последовательность из n = 10
битов можно представить степенным
полиномом, например вида Р(х) = х⁹
+ х⁵
+
х²
+
1, который
представляет собой информационное
кодовое слово 1000100101. Разделим теперь
Р(х)
на порождающий
полином, называемый также генераторным
полиномом G(x).
Результатом
деления будут частное Q(x)
и остаток
R(х).

Возьмем в качестве
генераторного полинома G(x) = х⁵
+ x⁴
+ + х²
+ 1, представляющий
двоичное число 110101. Перемножим Р(х)
и первый
член полинома G(x),
имеющий
наивысшую степень, а полученный результат
затем разделим на G(x):

Выполним эти
вычисления

Передаваемое
кодовое слово D(x)
в этом случае
имеет вид

в примере
соответственно 1 0 0 0 1 0 0 1 0 1 0 0 0 1 1.
Декодирующее устройство делит эти биты
данных на G(x),
и если новый
остаток R‘(x) = 0,
то передача свободна от ошибок (без
ошибок). В противном случае из остатка
можно локализовать ошибку.

В качестве примера
на рис. 1.23
показаны структурные схемы кодирующего
и декодирующего устройств с использованием
циклического кода (29,24). Порождающий
многочлен этого кода имеет вид F₁(x) = x⁵
+ x²
+ 1. Первоначально (рис. 1.23,
а) ключ К
замкнут и на вход схемы последовательно
подаются информационные символы.
Одновременно эти же символы поступают
на выход. Кодер представляет собой здесь
многотактный линейный фильтр Хаффмена,
состоящий из элементов 1 — 5 сдвигового
регистра и двух сумматоров C1
и С2. Данное устройство выполняет деление
полинома x⁵G(x)
на порождающий
полином F₁(x).
После 24-х
тактов работы кодера в его регистре
образуется остаток q(x)
от деления.
На 25-м такте ключ К перебрасывается в
верхнее положение, и символы остатка
(поверочные символы) один за другим
поступают на выход кодера. За пять тактов
на выход поступают пять поверочных
символов и происходит обнуление регистра.
Затем происходит кодирование следующей
группы информационных символов.

Рис. 1.23
— Пример структурных схем кодера (а)
и декодера (б)

с использованием
циклического кода (29,24)

Принятый декодером
(рис. 1.23,
б) входной
сигнал запоминается регистром сдвига
PC
и одновременно через ключ К поступает
на устройство деления УД, подобное тому,
которое имеется в кодере. После поступления
в УД 29-ти символов (блок данного кода)
ключ К перебрасывается в нижнее положение
и поступление входного сигнала на УД
прекращается. Одновременно с выхода УД
сигнал поступает на детектор ошибки.
Если принятое кодовое слово не имеет
ошибок, то на выходе УД имеется нулевой
сигнал, что и фиксирует детектор, разрешая
без коррекции информационным символам
покидать PC
через сумматор С₃.
Если принято ошибочное кодовое слово,
то на выходе УД имеется ненулевой сигнал.
В этом случае продолжающийся тактовый
сдвиг разрядов сигнала в регистре УД
приводит к появлению кодового слова,
соответствующего эталонному полиному.
В тот же момент в детекторе формируется
исправляющий сигнал, который соответствует
положению ошибки в информационных
символах, проходящих через сумматор
С₃.
Исправляющий символ, поступающий от
детектора ошибок, исправляет ошибочный
информационный символ.

Подклассом
циклических кодов являются широко
распространенные коды
БЧХ (Боуза–Чоудхори–Хоквингема).
Для них справедливо правило: для любых
значений s
и q
< (2^s – 1)/2
существует двоичный циклический код
длиной n = 2^s – 1,
исправляющий все комбинации из q
или меньшего
числа ошибок и содержащий не более чем
sq
проверочных
символов. Так, код БЧХ (63,44), используемый
в системе спутникового цифрового
радиовещания, позволяет исправить две
или три ошибки, обнаружить и замаскировать
пять или четыре ошибки на каждый кодовый
блок из 63-х символов. При вероятности
ошибки р_ош = 10^–3
это означает появление одной необнаруженной
ошибки в час. Избыточность данного кода
составляет R = (63 – 44)/63 = 0,33
(33 %). Такой же избыточностью обладают и
циклические
коды Рида–Соломона. Двойной
код Рида–Соломона с перемежением
символов (CIRC-код)
как наиболее эффективный при исправлении
ошибок большой кратности нашел применение
в системе компакт-диска и цифровой
магнитной записи.

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

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

Перемежение старших
и младших разрядов в пределах одного
отсчета используется очень часто. При
этом младшие разряды, число которых
обычно равно или составляет более
половины всех разрядов отсчета,
размещаются равномерно между старшими
разрядами (рис. 1.24,
а). Здесь
кодовое слово является 12-сим-вольным,
из которых 11 информационных разрядов
(а1, a2…а11)
и один (b1)
— поверочный, определяемый как сумма
по модулю 2 пяти старших информационных
разрядов (a1,
а2…a5).
Поверочный разряд находится на последней
позиции, а самый младший 11-й разряд —
на первой. В этом случае пакеты ошибок,
состоящие из двух символов, и около 40 %
пакетов ошибок длительностью в три
символа приводят к появлению одиночной
(односимвольной) ошибки на выходе
декодера.

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

Рис. 1.24
— К перемежению символов при защите от
ошибок:

а — перемежение
разрядов внутри 12-символьного кодового
слова;

б — перемежение
разрядов разных отсчетов; в
— перемежение старших

и младших разрядов
в восьми 10-разрядных отсчетах

В отсутствии
перемежения (строка 1) эти ошибки исказят
подряд символы а7,
a8,
б1,
б2,
б3,
б4,
б5.
Если же пакет
ошибок возник у сигнала, подвергнутого
перемежению (строка 2), то из строки 3
видно, что после операции, обратной
перемежению, пакет ошибок превратился
в совокупность одиночных ошибок, с
которым можно бороться уже описанными
выше способами.

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

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

Рис. 1.25
— К пояснению принципа перемежения
отсчетов:

а — без
перемежения; б
— с
перемежением; 1
— исходный
аналоговый ЗС; 2
— отсчеты дискретизированного сигнала
(а
— без перемежения; б
—

с перемежением);
3 — пропадание
соседних отсчетов при считывании;

4 — восстановленные
отсчеты (а
— без перемежения,
б — с
перемежением); штриховой линией показаны
потерянные отсчеты при считывании,

их восстановление
возможно путем интерполяции

Размещение цифрового
ЗС в канальных интервалах цикла цифровой
системы передачи обычно производят
емкостью в один октет. Для примера на
рис. 1.24,
в
показано
перемежение восьми 10-разрядных отсчетов.
В первом октете размещены 1-й и 10-й разряды
первых четырех нечетных отсчетов, во
втором октете — 2-й и 9-й разряды тех же
отсчетов и т.д. Затем подобным же образом
перемежаются разряды четырех четных
отсчетов. При разделении отсчетов на
четные и нечетные пакет ошибок
длительностью в восемь символов не
приводит к одновременному искажению
соседних отсчетов. Последнее позволяет
использовать далее интерполяцию нулевого
или первого порядка при коррекции
восстановленных отсчетов.

Содержание

Задание

Виды способов управления ошибками

Метод эхо-контроля

Механизм передачи “бездействие – ЗПР”

Механизм передачи “непрерывная передача – ЗПР”

Описание последовательности передачи кадров в механизме обмена данными “возврат-к-N” при наличии искажений I-кадра и ACK-кадра

Описание временных параметров задержки в канале связи при передаче информации между ПС и ВС

Описание механизма тайм-аута и механизма окна

Механизм тайм-аута

Механизм окна

Расчет эффективности использования пропускной способности канала связи

Исследование зависимости величины эффективности использования канала связи от его пропускной способности

Исследование зависимости величины эффективности канала связи от длины передаваемых пакетов

Нахождение максимальной длины физического канала связи, при которой его эффективность близка к 100%, а коэффициент “а” остается меньше 1

Анализ и определение скорости передачи и длины кадра, при которых эффективность использования канала связи максимальна

Выводы

Задание

Исходные данные для расчета:

– тип канала связи: радиоэфир (спутниковая связь), (м/с);

– длина канала связи (м);

– скорость передачи информации (Мбит/сек);

– длина кадра (бит);

– размер окна ;

– вероятность искажения одного бита ;

– режим обмена – “возврат-к-N”.

Виды способов управления ошибками

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

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

Метод эхо-контроля

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

—> ЧИТАТЬ ПОЛНОСТЬЮ <—

К-во Просмотров: 269

Бесплатно скачать Курсовая работа: Управление ошибками при передаче информации по каналам связи

5.1. Понятие о корректирующих кодах

5.2. Циклические коды

5.3. Выбор образующего полинома циклического кода

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

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

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

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

5.1. Понятие о корректирующих кодах

Пусть имеется источник сообщений с объемом алфавита К.

Поставим в соответствие каждому сообщению n — элементную двоичную последовательность. Всего последовательностей из n — элементов может быть .

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

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

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

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

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

Перебрав все возможные пары разрешенных комбинаций рассматриваемого кода можно найти минимальное расстояние Хемминга d₀.

Минимальное расстояние d₀ — называется кодовым расстоянием

Кодовое расстояние определяет способность кода обнаруживать и исправлять ошибки.

У простого кода d₀=1 – он не обнаруживает и не исправляет ошибки. Так как любая ошибка переводит одну разрешенную комбинацию в другую.

В общем случае справедливы следующие соотношения

– для обнаруживающей способности

– для исправляющей способности

Линейные коды

Двоичный блочный код является линейным если сумма по модулю 2 двух кодовых слов является также кодовым словом.

Линейные коды также называют групповыми.

Введем понятия группы.

Множество элементов с определенной на нем групповой операцией называется группой, если выполняется следующие условия:

1. Замкнутость g_ig _j= g_k G в результате операции с двумя элементами группы получается третий, так же принадлежащий этой группе.
2. Ассоциативность (сочетательность) (g_ig_j) g_k = g_i (g_j g_k)
3. Наличие нейтрального элемента g_j e = g_j
4. Наличие обратного элемента. g_i (g_i)^-1= e

Если выполняется условие g_i g_j = g_j g_i, то группа называется коммутативной.

Множество кодовых комбинаций n-элементного кода является замкнутой группой с заданной групповой операцией сложение по модулю 2.

Поэтому используя свойство замкнутости относительно операции 2, множество всех элементов можно задать не перечислением всех элементов, а производящей матрицей.

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

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

5.2. Циклические коды

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

если некоторая кодовая комбинация принадлежит циклическому коду, то комбинация полученная циклической перестановкой исходной комбинации (циклическим сдвигом), также принадлежит данному коду.

.

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

Синдромом ошибки в этих кодах является наличие остатка от деления принятой кодовой комбинации на производящий полином.

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

Представление кодовой комбинации в виде многочлена

Описание циклических кодов и их построение удобно проводить с помощью многочленов (или полиномов).

В теории циклических кодов кодовые комбинации обычно представляются в виде полинома. Так, n-элементную кодовую комбинацию можно описать полиномом (n-1) степени, в виде

.

где ={0,1}, причем = 0 соответствуют нулевым элементам комбинации, а = 1 — ненулевым.

Запишем полиномы для конкретных 4-элементных комбинаций

Действия над многочленами

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

,

поскольку .

Следует отметить, что действия над коэффициентами полинома (сложение и умножение) производятся по модулю 2.

Рассмотрим операцию деления на следующем примере:

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

Отметим, что запись кодовой комбинации в виде многочлена, не всегда определяет длину кодовой комбинации. Например, при n = 5, многочлену соответствует кодовая комбинация 00011.

Алгоритм получения разрешенной кодовой комбинации циклического кода из комбинации простого кода

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

Требуется определить разрешенную кодовую комбинацию циклического кода (n, k).

• Умножаем многочлен исходной кодовой комбинации на

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

• Окончательно разрешенная кодовая комбинация циклического кода определится так

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

Формирование базиса (производящей матрицы) циклического кода

Формирование базиса циклического кода возможно как минимум двумя путями.

Вариант первый.

1. Составить единичную матрицу для простого исходного кода.
2. Определить для каждой кодовой комбинации исходного кода группу проверочных элементов и дописать их в соответствующие строки матрицы.

Полученная матрица и будет базисом циклического кода. Причем, в данном случае, разрешенные комбинации заведомо разделимы (т.е. информационные и проверочные элементы однозначно определены).

Вариант второй.

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

• Получить остальные разрешенные кодовые КК базиса, используя циклический сдвиг исходной. (В базисе должно быть k – строк)

В данном случае код будет неразделимым.

Получив базис ЦК, можно получить все разрешенные комбинации, проводя сложение по модулю 2 кодовых комбинаций базиса в различных сочетаниях и плюс НУЛЕВАЯ.

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

Построение кодера циклического кода

Рассмотрим код (9,5) образованный полиномом

.

Разрешенная комбинация циклического кода образуется из комбинации простого (исходного) кода путем умножения ее на и прибавления остатка R(x) от деления на образующий полином.

• Умножение полинома на одночлен

эквивалентно добавлению к двоичной последовательности соответствующей G(x) , r — нулей справа.

Пусть

тогда

Для реализации операции добавления нулей используется r-разрядный регистр задержки.

• Рассмотрим более подробно операцию деления:

Как видим из примера, процедура деления одного двоичного числа на другое сводится к последовательному сложению по mod2 делителя [10011] с соответствующими членами делимого [10101], затем с двоичным числом, полученным в результате первого сложения, далее с результатом второго сложения и т.д., пока число членов результирующего двоичного числа не станет меньше числа членов делителя.

Это двоичное число и будет остатком .

Построение формирователя остатка циклического кода

Структура устройства осуществляющего деление на полином полностью определяется видом этого полинома. Существуют правила позволяющие провести построение однозначно.

Сформулируем правила построения ФПГ.

1. Число ячеек памяти равно степени образующего полинома r.
2. Число сумматоров на единицу меньше веса кодирующей комбинации образующего полинома.
3. Место установки сумматоров определяется видом образующего полинома.

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

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

Структурная схема кодера циклического кода (9,5)

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

Рассмотрим работу этой схемы

1. На первом этапе К₁– замкнут К₂ – разомкнут. Идет одновременное заполнение регистров задержки и сдвига информ. элементами (старший вперед!) и через 4 такта старший разряд в ячейке №4

2. Во время пятого такта К₂ – замыкается а К₁ – размыкается с этого момента в ФПГ формируется остаток. Одновременно из РЗ на выход выталкивается задержание информационные разряды.

За 5 тактов (с 5 по 9 включительно) в линию уйдут все 5-информационных элемента. К этому времени в ФПГ сформируется остаток

3. К₂ – размыкается, К₁ – замыкается и в след за информационными в линию уйдут элементы проверочной группы.

4. Одновременно идет заполнение регистров новой комбинацией.

Второй вариант построения кодера ЦК

Рассмотренный выше кодер очень наглядно отражает процесс деления двоичных чисел. Однако можно построить кодер содержащий меньшее число элементов т.е. более экономичный.

Устройство деления на производящий полином можно реализовать в следующем виде:

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

За эти же 5 тактов информационные разряды, выданные сразу на модулятор.

Далее в след за информационными уходят проверочные из ячеек устройств деления.

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

Окончательно структурная схема экономичного кодера выглядит так.

— На первом такте Кл.1 и Кл.3 замкнуты, информационные элементы проходят на выход кодера и одновременно формируются проверочные элементы.

— После того, как в линию уйдет пятый информационный элемент, в устройстве деления сформируются проверочные;

— на шестом такте ключи 1 и 3 размыкаются (разрываются обратная связь), а ключ 2 замыкается и в линию уходят проверочные разряды.

Ячейки при этом заполняются нулями и схема возвращается в исходное состояние.

Определение ошибочного разряда в ЦК

Пусть А(х)-многочлен соответствующий переданной кодовой комбинации.

Н(х)- многочлен соответствующей принятой кодовой комбинацией.

Тогда сложение данных многочленов по модулю два даст многочлен ошибки.

E(x)=A(x) H(x)

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

Остаток – полученный от деления принятого многочлена H(x) на производящей P_r(x) равен остатку полученному при делении соответствующего многочлена ошибок E(x) на P_r(x)

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

Алгоритм определения ошибки

Пусть имеем n-элементные комбинации (n = k + r) тогда:

1. Получаем остаток от деления Е(х) соответствующего ошибке в старшем разряде [1000000000], на образующей поленом P_r(x)

2. Делим полученный полином Н(х) на P_r(x) и получаем текущий остаток R(x).

3. Сравниваем R₀(x) и R(x).

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

— Если «нет», то увеличиваем степень принятого полинома на Х и снова проводим деления

в) Опять сравниваем полученный остаток с R₀(x)

— Если они равны, то ошибки во втором разряде.

— Если нет, то умножаем Н(х)х² и повторяем эти операции до тех пор, пока R(X) не будет равен R₀(x).

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

Например: то номер ошибочного разряда 3+1=4

Пример декодирования комбинации ЦК

Положим, получена комбинация H(х)=111011010

Проанализируем её в соответствии с вышеприведенным алгоритмом.

Реализуя алгоритм определения ошибок, определим остаток от деления вектора соответствующего ошибке в старшем разряде Х⁸ на производяший полином P(x)=X⁴+X+1

X⁸ X²+X+1

X⁸+X⁵+X⁴ x⁴+x+1

X⁵+X⁴

X⁵+X²+X

X⁴+X²+X

X⁴+X+1

X²+1=R₀(X)=0101

Разделим принятую комбинацию на образующий полином

Полученный на 9-м такте остаток, как видим, не равен R₀(X). Значит необходимо умножить принятую комбинацию на Х и повторить деление. Однако результаты деления с 5 по 9 такты включительно будут такими же, значит необходимо продолжить деление после девятого такта до тех пор, пока в остатке не будет R₀(Х). В нашем случае это произойдет на 10 такте, при повышении степени на 1. Значит ошибки во втором разряде.

Декодер циклического кода с исправлением ошибки

Если ошибка в первом разряде, то остаток R₀(X)=10101 появления после девятого такта в ячейках ФПГ.

Если во втором по старшинству то после 10^го;
в третьем по старшинству то после 11^го;
в четвертом по старшинству то после 12^го
в пятом по старшинству то после 13^го
в шестом по старшинству то после 14^го
в седьмом по старшинству то после 15^го
в восьмом по старшинству то после 16^го
в девятом по старшинству то после 17^го.

На 10 такте старший разряд покидает регистр задержки и проходит через сумматор по модулю 2.

Если и этому моменту остаток в ФПГ=R₀(X), то логическая 1 с выхода дешифратора поступит на второй вход сумматора и старший разряд инвертируется.

В нашем случае инвертируется второй разряд на 11 такте.

5.3. Выбор образующего полинома

Рассмотрим вопрос выбора образующего полинома, который определяет корректирующие свойства циклического кода. В теории циклических кодов показано, что образующий полином представляет собой произведение так называемых минимальных многочленов m_i(x), являющихся простыми сомножителями (то есть делящимся без остатка лишь на себя и на 1) бинома xⁿ+ 1:

P(x)=m₁(x)* m₃(x)…m_j(x), (*)

где j = d₀ – 2 =( 2t_u.ош+1) – 2 = 2 t_и.ош – 1.

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

для любых значений l и t_и.ош существует циклический код длины n =2^l – 1, исправляющий все ошибки кратности t_и.ош и менее, и содержащий не более проверочных элементов.

Так как , то откуда . (**)

Очевидно, что для уменьшения времени передачи кодовых комбинаций, r следует выбирать как можно меньше. Пусть, например, длина кодовых комбинаций n = 7, кратность исправляемых ошибок t_и.ош =1. Из (**) получим r = 1 ^. log₂ ( 7+1 )=3.

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

Таблица минимальных многочленов

Определяя образующий полином, нужно из столбца для соответствующего соотношения выписать все многочлены, начиная с верхней строки до нижней с номером j=2t_и.ош–1 включительно. После этого следует перемножить выбранные минимальные многочлены в соответствии с (*). В частности, если r=3, t_и.ош=1, j=2*1-1=1, образующий полином будет представлять собой единственный минимальный многочлен P(x)= m₁(x) = x³+x+1 (первая строка, второй столбец таблицы ). Соответственно образующее число равно 1011.

Контрольные вопросы по теме:

1. Что такое разрешенные и запрещенные кодовые комбинации.
2. Что называется расстоянием Хемминга.
3. Дайте понятие кодового расстояния и как его определить.
4. Как связано кодовое расстояние с исправляющей и обнаруживающей способностью кода.
5. Какой код называется линейным.
6. Какое множество называется группой.
7. Назовите основные свойства циклических кодов.
8. Запишите полином в двоичном виде.
9. Запишите полином, соответствующий двоичной записи 100111.
10. Получите остаток от деления полинома на .
11. Как получают разрешенные комбинации при циклическом кодировании.
12. Нарисуйте кодер для циклического кода, порождаемого полиномом . Поясните принцип работы кодера.
13. По какому признаку обнаруживают ошибку в принятой кодовой комбинации.
14. Каков алгоритм определения ошибочного разряда в комбинации циклического кода.
15. Нарисуйте структурную схему декодера, обеспечивающего обнаружение ошибок для кода (7,4) при производящем полиноме . Поясните принцип его работы.
16. Нарисуйте структурную схему декодера, обеспечивающего исправление однократной ошибки для кода (7,4) при производящем полиноме . Поясните принцип его работы.
17. Как выбирается образующий (производящий) полином?

Методы, обеспечивающие надежную доставку цифровых данных по ненадежным каналам связи Устранение ошибок передачи, вызванных атмосферой Земли ( слева), ученые Годдарда применили исправление ошибок Рида – Соломона (справа), которое обычно используется в компакт-дисках и DVD. Типичные ошибки включают отсутствие пикселей (белые) и ложные сигналы (черные). Белая полоса указывает на короткий период, когда передача была приостановлена.

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

Содержание

• 1 Определения
• 2 История
• 3 Введение
• 4 Типы исправления ошибок
  • 4.1 Автоматический повторный запрос (ARQ)
  • 4.2 Прямое исправление ошибок
  • 4.3 Гибридные схемы
• 5 Схемы обнаружения ошибок
  • 5.1 Кодирование на минимальном расстоянии
  • 5.2 Коды повторения
  • 5.3 Бит четности
  • 5.4 Контрольная сумма
  • 5.5 Циклическая проверка избыточности
  • 5.6 Криптографическая хеш-функция
  • 5.7 Ошибка код исправления
• 6 Приложения
  • 6.1 Интернет
  • 6.2 Связь в дальнем космосе
  • 6.3 Спутниковое вещание
  • 6.4 Хранение данных
  • 6.5 Память с исправлением ошибок
• 7 См. также
• 8 Ссылки
• 9 Дополнительная литература
• 10 Внешние ссылки

Определения

Обнаружение ошибок — это обнаружение ошибок, вызванных шумом или другими помехами во время передачи от передатчика к приемнику. Исправление ошибок — это обнаружение ошибок и восстановление исходных безошибочных данных.

История

Современная разработка кодов исправления ошибок приписывается Ричарду Хэммингу в 1947 году. Описание кода Хэмминга появилось в Математической теории коммуникации Клода Шеннона и было быстро обобщено Марселем Дж. Э. Голэем.

Введение

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

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

Если характеристики канала не могут быть определены или сильно изменяются, схема обнаружения ошибок может быть объединена с системой для повторных передач ошибочных данных. Это известно как автоматический запрос на повторение (ARQ) и наиболее широко используется в Интернете. Альтернативный подход для контроля ошибок — это гибридный автоматический запрос на повторение (HARQ), который представляет собой комбинацию ARQ и кодирования с исправлением ошибок.

Типы исправления ошибок

Существует три основных типа исправления ошибок.

Автоматический повторный запрос (ARQ)

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

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

Три типа протоколов ARQ: Stop-and-wait ARQ, Go-Back-N ARQ и Selective Repeat ARQ.

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

Например, ARQ используется на коротковолновых радиоканалах в форме ARQ-E, или в сочетании с мультиплексированием как ARQ-M.

Прямое исправление ошибок

Прямое исправление ошибок (FEC) — это процесс добавления избыточных данных, таких как исправление ошибок code (ECC) в сообщение, чтобы оно могло быть восстановлено получателем, даже если в процессе передачи или при хранении был внесен ряд ошибок (в зависимости от возможностей используемого кода). Так как получатель не должен запрашивать у отправителя повторную передачу данных, обратный канал не требуется при прямом исправлении ошибок, и поэтому он подходит для симплексной связи, например вещание. Коды с исправлением ошибок часто используются в нижнем уровне связи, а также для надежного хранения на таких носителях, как CD, DVD, жесткие диски и RAM.

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

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

Теорема Шеннона — важная теорема при прямом исправлении ошибок и описывает максимальную информационную скорость, на которой возможна надежная связь по каналу, имеющему определенную вероятность ошибки или отношение сигнал / шум (SNR). Этот строгий верхний предел выражается в единицах пропускной способности канала . Более конкретно, в теореме говорится, что существуют такие коды, что с увеличением длины кодирования вероятность ошибки на дискретном канале без памяти может быть сделана сколь угодно малой при условии, что кодовая скорость меньше чем емкость канала. Кодовая скорость определяется как доля k / n из k исходных символов и n кодированных символов.

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

Гибридные схемы

Гибридный ARQ — это комбинация ARQ и прямого исправления ошибок. Существует два основных подхода:

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

Последний подход особенно привлекателен для канала стирания при использовании код бесскоростного стирания.

.

Схемы обнаружения ошибок

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

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

Кодирование с минимальным расстоянием

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

Коды повторения

A код повторения — это схема кодирования, которая повторяет биты по каналу для достижения безошибочной связи. Учитывая поток данных, которые необходимо передать, данные делятся на блоки битов. Каждый блок передается определенное количество раз. Например, чтобы отправить битовую комбинацию «1011», четырехбитовый блок можно повторить три раза, таким образом получая «1011 1011 1011». Если этот двенадцатибитовый шаблон был получен как «1010 1011 1011» — где первый блок не похож на два других, — произошла ошибка.

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

Бит четности

Бит четности — это бит, который добавляется к группе исходные биты, чтобы гарантировать, что количество установленных битов (т. е. битов со значением 1) в результате будет четным или нечетным. Это очень простая схема, которую можно использовать для обнаружения одного или любого другого нечетного числа (т. Е. Трех, пяти и т. Д.) Ошибок в выводе. Четное количество перевернутых битов сделает бит четности правильным, даже если данные ошибочны.

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

Контрольная сумма

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

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

Проверка циклическим избыточным кодом

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

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

. Бит четности может рассматриваться как 1-битный частный случай. CRC.

Криптографическая хеш-функция

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

Код исправления ошибок

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

Коды с минимальным расстоянием Хэмминга d = 2 являются вырожденными случаями кодов с исправлением ошибок и могут использоваться для обнаружения одиночных ошибок. Бит четности является примером кода обнаружения одиночной ошибки.

Приложения

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

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

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

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

Надежность и инженерная проверка также используют теорию кодов исправления ошибок.

Интернет

В типичном стеке TCP / IP ошибка управление осуществляется на нескольких уровнях:

• Каждый кадр Ethernet использует CRC-32 обнаружение ошибок. Фреймы с обнаруженными ошибками отбрасываются оборудованием приемника.
• Заголовок IPv4 содержит контрольную сумму , защищающую содержимое заголовка. Пакеты с неверными контрольными суммами отбрасываются в сети или на приемнике.
• Контрольная сумма не указана в заголовке IPv6, чтобы минимизировать затраты на обработку в сетевой маршрутизации и поскольку предполагается, что текущая технология канального уровня обеспечивает достаточное обнаружение ошибок (см. также RFC 3819 ).
• UDP, имеет дополнительную контрольную сумму, покрывающую полезную нагрузку и информацию об адресации в заголовки UDP и IP. Пакеты с неверными контрольными суммами отбрасываются сетевым стеком . Контрольная сумма не является обязательной для IPv4 и требуется для IPv6. Если не указано, предполагается, что уровень канала передачи данных обеспечивает желаемый уровень защиты от ошибок.
• TCP обеспечивает контрольную сумму для защиты полезной нагрузки и адресной информации в заголовках TCP и IP. Пакеты с неверными контрольными суммами отбрасываются сетевым стеком и в конечном итоге повторно передаются с использованием ARQ либо явно (например, как через тройное подтверждение ) или неявно из-за тайм-аута .

Телекоммуникации в дальнем космосе

Разработка кодов исправления ошибок была тесно связана с историей полетов в дальний космос из-за сильного ослабления мощности сигнала на межпланетных расстояниях и ограниченной мощности на борту космических зондов. В то время как ранние миссии отправляли свои данные в незашифрованном виде, начиная с 1968 года, цифровая коррекция ошибок была реализована в форме (субоптимально декодированных) сверточных кодов и кодов Рида – Маллера. Код Рида-Мюллера хорошо подходил к шуму, которому подвергался космический корабль (примерно соответствуя кривой ), и был реализован для космического корабля Mariner и использовался в миссиях между 1969 и 1977 годами.

Миссии «Вояджер-1 » и «Вояджер-2 «, начатые в 1977 году, были разработаны для доставки цветных изображений и научной информации с Юпитера и Сатурна. Это привело к повышенным требованиям к кодированию, и, таким образом, космический аппарат поддерживался (оптимально Витерби-декодированный ) сверточными кодами, которые могли быть сцеплены с внешним Голеем (24,12, код. Корабль «Вояджер-2» дополнительно поддерживал реализацию кода Рида-Соломона. Конкатенированный код Рида – Соломона – Витерби (RSV) позволил произвести очень мощную коррекцию ошибок и позволил космическому кораблю совершить длительное путешествие к Урану и Нептуну. После модернизации системы ECC в 1989 году оба корабля использовали кодирование V2 RSV.

Консультативный комитет по космическим информационным системам в настоящее время рекомендует использовать коды исправления ошибок, как минимум, аналогичные RSV-коду Voyager 2. Составные коды все больше теряют популярность в космических миссиях и заменяются более мощными кодами, такими как Турбо-коды или LDPC-коды.

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

Спутниковое вещание

Спрос на пропускную способность спутникового транспондера продолжает расти, чему способствует желание предоставлять телевидение (включая новые каналы и телевидение высокой четкости ) и данные IP. Доступность транспондеров и ограничения полосы пропускания ограничили этот рост. Емкость транспондера определяется выбранной схемой модуляции и долей мощности, потребляемой FEC.

Хранение данных

Коды обнаружения и исправления ошибок часто используются для повышения надежности носителей данных. «Дорожка четности» присутствовала на первом устройстве хранения данных на магнитной ленте в 1951 году. «Оптимальный прямоугольный код», используемый в записи с групповым кодированием, не только обнаруживает, но и корректирует однобитовые записи. ошибки. Некоторые форматы файлов, особенно архивные форматы, включают контрольную сумму (чаще всего CRC32 ) для обнаружения повреждений и усечения и могут использовать избыточность и / или четность files для восстановления поврежденных данных. Коды Рида-Соломона используются в компакт-дисках для исправления ошибок, вызванных царапинами.

Современные жесткие диски используют коды CRC для обнаружения и коды Рида – Соломона для исправления незначительных ошибок при чтении секторов, а также для восстановления данных из секторов, которые «испортились», и сохранения этих данных в резервных секторах. Системы RAID используют различные методы исправления ошибок для исправления ошибок, когда жесткий диск полностью выходит из строя. Файловые системы, такие как ZFS или Btrfs, а также некоторые реализации RAID, поддерживают очистку данных и восстановление обновлений, что позволяет удалять поврежденные блоки. обнаружены и (надеюсь) восстановлены, прежде чем они будут использованы. Восстановленные данные могут быть перезаписаны точно в том же физическом месте, чтобы освободить блоки в другом месте на том же оборудовании, или данные могут быть перезаписаны на заменяющее оборудование.

Память с исправлением ошибок

Память DRAM может обеспечить более надежную защиту от программных ошибок, полагаясь на коды исправления ошибок. Такая память с исправлением ошибок, известная как память с защитой ECC или EDAC, особенно желательна для критически важных приложений, таких как научные вычисления, финансы, медицина и т. Д., А также для приложений дальнего космоса из-за повышенное излучение в космосе.

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

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

Помимо оборудования, обеспечивающего функции, необходимые для работы памяти ECC, операционные системы обычно содержат соответствующие средства отчетности, которые используются для предоставления уведомлений при прозрачном восстановлении программных ошибок. Увеличение количества программных ошибок может указывать на то, что модуль DIMM нуждается в замене, и такая обратная связь не была бы легко доступна без соответствующих возможностей отчетности. Одним из примеров является подсистема EDAC ядра Linux (ранее известная как Bluesmoke), которая собирает данные из компонентов компьютерной системы, поддерживающих проверку ошибок; Помимо сбора и отправки отчетов о событиях, связанных с памятью ECC, он также поддерживает другие ошибки контрольного суммирования, в том числе обнаруженные на шине PCI.

Некоторые системы также поддерживают очистку памяти.

См. также

Ссылки

Дополнительная литература

• Шу Линь; Дэниел Дж. Костелло младший (1983). Кодирование с контролем ошибок: основы и приложения. Прентис Холл. ISBN 0-13-283796-X.

Внешние ссылки