Система передачи дискретных сообщений

КОДИРОВАНИЕ СИГНАЛОВ

1.1 основные понятия

Кодирование – преобразование элементов дискретного сообщения в последовательности кодовых символов. Обратное преобразование – декодирование.

Устройства, осуществляющие эти операции автоматически, называются соответственно кодером и декодером. Кодек – устройство, объединяющее кодер и декодер.

Код – алгоритм (правило), по которому осуществляется кодирование.

Кодовая комбинация (слово) – последовательность кодовых символов, соответствующая одному элементу дискретного сообщения.

Кодовый алфавит – весь набор кодовых символов.

Основание кода m – число символов в кодовом алфавите. Если m=2 код называется двоичным, m>2 – многопозиционным (недвоичным).

Разряд – значащая позиция кодового слова.

Разрядность (значность) кода n – число символов в кодовой комбинации. Если n =const, то код называется равномерным, n≠const – неравномерным.

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

 

Система передачи дискретных сообщений

Рисунок 1.1 – Структурная схема системы передачи дискретных сообщений.

 

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

Кодирование источника (сжатие данных) применяется для снижения технических затрат на хранение и передачу информации.

Криптографическое кодирование (шифрование) применяется для предотвращения несанкционированного доступа к информации.

Кодирование канала (помехоустойчивое кодирование) применяется для повышения достоверности передачи информации по каналу с помехами.

 

Сжатие данных

Сжатие возможно, т.к. данные на выходе источника содержат избыточную и/или плохо различимую информацию.

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

Приемы, применяемые в алгоритмах сжатия с потерями:

- использование модели – подбор параметров модели и передача только одних параметров;

- предсказание – предсказание последующего элемента и передача величины ошибки;

- дифференциальное кодирование – передача изменений последующего элемента при сравнении с предыдущим.

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

Приемы, применяемые в алгоритмах сжатия без потерь:

- кодирование длин последовательностей – передача числа повторяющихся элементов;

- кодирование словаря – использование ссылок на переданные ранее последовательности, а не их повторение;

- неравномерное кодирование – более вероятным символам присваиваются более короткие кодовые слова.

Кодирование словаря

Позволяет уменьшить избыточность, вызванную зависимостью между символами. Идея кодирования словаря состоит в замене часто встречающихся последовательностей символов ссылками на образцы, хранящиеся в специально создаваемой таблице (словаре). Данный подход основан на алгоритме LZ, описанном в работах израильских исследователей Зива и Лемпеля.

Неравномерное кодирование

Позволяет уменьшить избыточность, вызванную неравной вероятностью символов. Идея неравномерного кодирования состоит в использовании коротких кодовых слов для часто встречающихся символов и длинных – для редко возникающих. Данный подход основан на алгоритмах Шеннона-Фано и Хаффмана.

Коды Шеннона-Фано и Хаффмана являются префиксными. Префиксный код – код, обладающий тем свойством, что никакое более короткое слово не является началом (префиксом) другого более длинного слова. Такой код всегда однозначно декодируем. Обратное неверно.

Код Шеннона-Фано строится следующим образом. Символы источника выписываются в порядке убывания вероятностей (частот) их появления. Затем эти символы разбиваются на две части, верхнюю и нижнюю, так, чтобы суммарные вероятности этих частей были по возможности одинаковыми. Для символов верхней части в качестве первого символа кодового слова используется 1, а нижней – 0. Затем каждая из этих частей делится еще раз пополам и записывается второй символ кодового слова. Процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному символу.

Пример1.1:

Таблица 1.1 – Построение кода Шеннона-Фано.

Символ	Вероятность	Этапы разбиения	Код
а1 а2 а3 а4 а5	0,40 0,35 0,10 0,10 0,05

 

Алгоритм Шеннона-Фано не всегда приводит к построению однозначного кода с наименьшей средней длиной кодового слова. От отмеченных недостатков свободен алгоритм Хаффмана.

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

 

Пример1.2:

Таблица 1.2 – Построение кода Хаффмана.

Символ	Вероятность	Объединение символов	Код
а1 а2 а3 а4 а5	0,40 0,35 0,10 0,10 0,05	0,40 0,35 0,15 0,10	0,40 0,35 0,25	0,60 0,40	1,00

Рисунок 1.2 – Кодовое дерево для кода Хаффмана.

 

Домашнее задание:

1. [3.1.2] с.13…16;

[3.1.3] с.174…176;

[3.1.5] с. 109…112, 131…135, 297…299;

[3.1.14] с. 146…155;

[3.1.15] с.11…14.

2. Файл состоит из некоторой символьной строки:

«aaaaaaaaaabbbbbbbbccccccdddddeeeefff».

Закодировать символы кодами Шеннона-Фано и Хаффмана и оценить достигнутую степень сжатия.

 

РЕШЕНИЕ ЗАДАЧИ ДОМАШНЕГО ЗАДАНИЯ:

Рассчитаем частоты появления символов: υ (а)=10/36=0,28; υ (b)=8/36=0,22; υ (c)=6/36=0,17; υ (d)=5/36=0,14; υ (e)=4/36=0,11; υ (f)=0,08.

Таблица 1.3 – Построение кода Шеннона-Фано.

Символ	Частота	Этапы разбиения	Код
a b c d e f	0,28 0,22 0,17 0,14 0,11 0,08

Достигнутая в результате кодирования степень сжатия определяется коэффициентом сжатия:

,

где к₀ – первоначальный размер данных;

к_m – размер данных в сжатом виде.

При кодировании кодом Шеннона-Фано обеспечивается коэффициент сжатия:

36∙¯| log₂ 6|¯/(10∙2+8∙2+6∙3+5∙3+4∙3+3∙3)=108/90=1,2,

где 36 – количество символов в файле;

¯| log₂ 6|¯ - минимальная длина кодовой комбинации при кодировании равномерным кодом (¯|.|¯ обозначает ближайшее целое число, большее log ₂6);

10, 8, 6, 5, 4, 3 – число символов a, b, c, d, e, f в файле;

2, 2, 3, 3, 3, 3 – длина кодовых комбинаций кода Шеннона-Фано, соответствующих символам a, b, c, d, e, f (см. таблицу 1.1).

Таблица 1.3 – Построение кода Хаффмана.

Символ	Частота	Объединение символов	Код
a b c d e f	0,28 0,22 0,17 0,14 0,11 0,08	0,28 0,22 0,19 0,17 1,14	0,31 0,28 0,22 0,19	0,41 0,31 0,28	0,59 0,41	1,00

Рисунок 1.3 – Кодовое дерево для кода Хаффмана.

При кодировании кодом Хаффмана обеспечивается степень сжатия:

К_сж =36∙¯| log₂ 6|¯/(10∙2+8∙2+6∙3+5∙3+4∙3+3∙3)=108/90=1,2.

 

Код с постоянным весом

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

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

Пример 2.3:

Таким кодом является код МТК-3 – семиразрядный код, каждая кодовая комбинация которого содержит три единицы.

ДОМАШНЕЕ ЗАДАНИЕ:

1 [3.1.1] с.272…277;

[3.1.2] с.307…313;

[3.1.3] с.185…189, 193;

[3.1.5] с.137…144;

[3.1.14] с.49…52;

[3.1.15] с.12…23.

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

 

Основные понятия

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

Они задаются с помощью порождающей и проверочной матриц, которые связаны основным уравнением кодирования:

,

где - транспонированная проверочная матрица (строки переписаны в столбцы );

- нулевая матрица.

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

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

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

Пример 3.1:

Код Рида-Маллера (8, 4) задается следующей порождающей матрицей:

.

 

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

Чаще всего применяют систематические линейные коды. Такие коды задаются матрицами в систематической (приведено-ступенчатой или канонической) форме:

,

где , - единичные подматрицы размерностью и соответственно;

- прямоугольная подматрица размерностью ;

- прямоугольная подматрица размерностью .

Пример 3.2:

Систематический код Рида-Маллера (8, 4) задается порождающей матрицей:

.

Найдем проверочную матрицу:

.

Кодирование информации

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

,

где - кодовый вектор.

Пример 3.3:

Рассмотрим кодирование информационного слова кодом Рида-Маллера (8, 4):

=(11000011).

2) С помощью матрицы : в СЛБК информационные символы слова входят без изменения в кодовое слово и занимают в нем первые позиций, к ним добавляются проверочных символов, правила формирования которых задает проверочная матрица.

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

Пример 3.4:

Из матрицы систематического кода Рида-Маллера запишем правила формирования проверочных символов:

,

,

,

.

Тогда для .

Код с четным числом единиц

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

Порождающая и проверочная матрицы такого кода:

,

.

Уравнение кодирования: .

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

Коды хэмминга

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

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

Примеры полных кодов Хэмминга: (7, 4), (15, 11), (31, 26), (63, 57).

Пример 3.5:

Рассмотрим код Хэмминга (7, 4). Проверочная матрица:

Порождающая матрица:

.

Модификациями кодов Хэмминга являются укороченные и удлиненные коды Хэмминга.

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

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

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

ЦИКЛИЧЕСКИЕ КОДЫ

Основные понятия

Поиск более простых процедур кодирования и декодирования привел к появлению циклических кодов.

Циклические коды – линейные блочные коды, обладающие свойством цикличности: если - кодовое слово циклического кода, то его циклическая перестановка также является кодовым словом.

Пример 4.1:

.

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

Все преобразования кодовых слов циклических кодов производятся в виде математических операций над полиномами (многочленами). Для этого кодовые слова представляются в форме полиномов:

,

где - коэффициенты полинома;

- символическая переменная.

Пример 4.2:

.

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

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

Любой полином степени , который делит без остатка полином вида , называется порождающим полиномом:

,

где - коэффициенты полинома.

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

Порождающая матрица строится на основе полинома .

Для несистематического циклического кода:

.

Для систематического циклического кода:

,

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

Пример 4.3:

Показать, что полином является порождающим для 7-разрядного циклического кода. Записать матрицу .

Для несистематического кода:

.

Для систематического кода:

.

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

,

где - коэффициенты полинома.

При отсутствии ошибок в принятом кодовом слове остаток от деления произведения на полином вида равен нулю:

.

Проверочная матрица строится на основе полинома .

Для несистематического циклического кода:

Для систематического циклического кода:

.

ДОМАШНЕЕ ЗАДАНИЕ:

2. Найти полином для задачи из примера 4.3. Записать матрицу .

 

Кодирование информации

Существует два способа кодирования:

- несистематическое кодирование:

,

где - полином информационного слова,

- полином кодового слова;

- систематическое кодирование:

,

где - остаток от деления произведения на полином .

Пример 4.3:

Закодировать слово циклическим кодом из примера 4.3.

Несистематическое кодирование:

.

Систематическое кодирование:

1) ;

2) ;

3) .

Кодирующие устройства

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

Правила построения схем умножения и деления:

- число ячеек памяти равно старшей степени полинома . Ячейка для старшей степени отсутствует;

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

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

Рисунок 4.1 – Кодер несистематического циклического кода.

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

Рисунок 4.2 – Кодер систематического циклического кода.

Кодер реализует алгоритм . Вначале ключ находится в положении 1, а ключ замкнут. Информационные символы, подаваемые на вход, через ключ поступают на выход, а через ключ - в кодирующее устройство, где через тактов образуется проверочных символов, представляющих собой остаток от деления произведения на полином . Затем ключ переводится в положение 2, а ключ размыкается. Регистр делает тактов, выдавая проверочные символы на выход.

Пример 4.4:

1 Построить схему кодера циклического кода из примера 4.3.

Рисунок 4.3 – Кодер несистематического кода.

2 Схему кодера систематического кода построить самостоятельно.

 

ДОМАШНЕЕ ЗАДАНИЕ:

1. [3.1.2] с.315…318;

[3.1.3] с.200…204;

[3.1.5] с.149…150;

[3.1.14] с.263…270, 282…286.

Мажоритарное декодирование

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

Существует три способа построения систем проверочных уравнений для декодирования символа:

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

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

- системы с квазиразделенными проверками – система разделима относительно некоторой суммы символов. На первом этапе она разрешается относительно суммы символов, а на втором – относительно конкретного символа.

Рисунок 5.2 – Структурная схема мажоритарного декодера.

На рисунке: 1…k – устройства, реализующие проверки для соответствующей системы; МЭ – мажоритарный элемент, принимающий решение о значении символа по большинству результатов проверок.

Пример 5.1:

Код (8,4) задан матрицей:

.

Система уравнений по матрице Н:

Система проверочных уравнений для :

Система проверочных уравнений для :

Система проверочных уравнений для :

Система проверочных уравнений для :

Пусть .

Результат декодирования: .

Декодирование по синдрому

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

Таблица – Стандартная таблица.

s1 =(0…0) r	b1 =(0…0) n	b2	…	bM
s2 … sN	e2 … eN	b2+e2 … b2+eN	… … …	bM+e2 … bM+eN

b _i – кодовые слова;

e _j – векторы ошибок – образцы ошибок минимального веса;

b _i+ e _j – слова, не являющиеся кодовыми;

s _i= e _i∙H^T – синдромы – векторы размерностью r, указывающие на наличие и расположение ошибок в принятом слове.

Правило декодирования:

1. Вычисляется синдром по принятому слову :

.

Если , то является кодовым словом. В противном случае () содержит ошибки.

2. По находится наиболее правдоподобный вектор ошибки .

3. Ближайшее к принятому кодовое слово получается в результате суммирования и :

.

Рисунок 5.3 – Структурная схема декодера по синдрому.

На рисунке: Б – буфер хранения принятого слова; БВС – блок вычисления синдрома; С – селектор (дешифратор) синдрома; К – корректор.

Данный метод используется, когда число проверочных символов мало (<10).

Пример:

Составить стандартную таблицу для систематического кода (5,2) с порождающей матрицей:

.

Таблица должна содержать строк и столбцов.

Таблица – Стандартная таблица.

b1 =(00000)	b2 =(01011)	b3 =(10101)	b4 =(11110)	s1 =(000)
e2 =(00001)	b2+e2 =(01010)	b3+e2 =(10100)	b4+e2 =(11111)	s2=e2∙H^T =(001)
e3 =(00010)	b2+e3 =(01001)	b3+e3 =(10111)	b4+e2 =(11100)	s3=e3 ∙ H^T =(010)
e4 =(00100)	b2+e4 =(01111)	b3+e4 =(10001)	b4+e2 =(11010)	s4=e4∙H^T =(100)
e5 =(01000)	b2+e5 =(00011)	b3+e5 =(11101)	b4+e2 =(10110)	s5=e5∙H^T =(011)
e6 =(10000)	b2+e6 =(11011)	b3+e6 =(00101)	b4+e2 =(01110)	s6=e6∙H^T =(101)
e7 =(01100)	b2+e7 =(00111)	b3+e7 =(11001)	b4+e2 =(10010)	s7=e7∙H^T =(111)
e8 =(11000)	b2+e8 =(10011)	b3+e8 =(01101)	b4+e2 =(00110)	s8=e8∙H^T =(110)

Пусть (10111). Проведем декодирование.

1. ;

2. ;

3. .

ДОМАШНЕЕ ЗАДАНИЕ:

1. [3.1.2] с. 309…312, 317…318;

[3.1.3] с. 205…208;

[3.1.5] с. 147.. 149, 150…151;

[3.1.14] с. 258…261, 271…273.

2. Код (7,4) задан порождающей матрицей:

.

Провести декодирование по синдрому принятого слова .

 

6 НЕПРЕРЫВНЫЕ (РЕКУРРЕНТНЫЕ) КОДЫ

Общие сведения

Непрерывные коды используют непрерывную обработку информации короткими фрагментами. Кодер для непрерывного кода обладает памятью, т.е. символы на его выходе зависят не только от очередного фрагмента информационных символов на входе, но и предыдущих символов на его входе и (или) выходе. Поэтому коды называются рекуррентными (recur – возвращаться, повторяться).

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

Пример 6.1:

Пакеты ошибок длиной 4 могут быть такими:

К непрерывным кодам относят цепной и сверточные. Цепной код является простейшим случаем сверточных.

 

Цепной код

В таком коде после каждого информационного символа следует проверочный. Закодированная последовательность имеет вид:

где - шаг сложения. Определяет корректирующие возможности кода;

- информационные символы;

- проверочные символы. Формируются по правилу: