Свойства циклических кодов по обнаружению ошибок

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

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

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

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

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

Существуют:

1)Укороченные циклические коды.

2) Циклические коды, исправляющие ошибки

2.1)Коды Боуза-Чоудхури-Хоквингема

2.2) Коды Рида-Соломона

2.3) Код Файра

Сверточные коды

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

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

Тогда последовательность символов на выходах кодера будет описываться многочленами: ;

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

Для приведенного выше примера порождающая матрица имеет вид:

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

Зная порождающие матрицу, выходную последовательность можно определить путем умножения вектора, характеризует входную последовательность на ;

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

При декодировании используют алгоритм Витерби.

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

7.9 Статичні методи стиснення інформації Алгоритм арифметичного стиснення.

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

Все методы сжатия информации основаны на двух стратегиях:

1) стратегия преобразования информации, где учитывается поведение сигнала на предыдущем интервале времени;

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

Арифметический код предназначен для сжатия без потерь на основе представления данных в виде чисел нормированных в интервале от 0 до 1.

Кодирование осуществляется в несколько этапов:

1) составление таблицы кода. Каждому символу выделяется интервал чисел внутри диапазона [0, 1], который пропорциональный вероятности данного символа. Например, слово РАДИОВИЗИР:

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

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

(для А: [0.8 + 0.2*0 = 0.8] – [0.8 + 0.1*0.2 = 0.82])

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

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