Кодирование в системах связи. Тема 3

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

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

Необратимое сжатие имеет гораздо более высокую степень сжатия, но допускает некоторые отклонения декодированных данных от исходных.
На практике существует широкий круг задач, в которых соблюдение требования точного восстановления исходной информации после декомпрессии не является обязательным.
Это, в частности, относится к сжатию мультимедийной информации: звука, фото- или видеоизображений.
Так, например, широко применяются форматы мультимедийной информации JPEG и MPEG, в которых используется необратимое сжатие.
Необратимое сжатие обычно не используется совместно с криптографическим шифрованием, так как основным требованием к криптосистеме является идентичность расшифрованных данных исходным.

3. Помехоустойчивое кодирование

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

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

2. Параметры кодов
Число m используемых для кодирования элементарных символов, определяет основание кода.
Коды с основанием m =2 называются двоичными.
В двоичном коде элементарные символы «1» и «0».
Коды с основанием m >2 называются многопозиционными.
Длина кодовой комбинации – n (разрядность кода).
Для кодов, имеющих одинаковую длину кодовой комбинации существует понятие кодового расстояния.

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

Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2.
1 1=0 1 0=1 0 1=1 0 0=0
Кодовая комбинация составляется из элементарных символов, например, при n=5 может быть представлена в виде 10101.
Число возможных комбинаций М при данных m и n:
М=mn.
Например, для кода Бодо (телеграфный код) при m=2, n=5
M=25=32.

Пример: рассмотрим обычный (не помехоустойчивый) трехразрядный двоичный код.
Для него возможное количество кодовых комбинаций M=23=8 и все комбинации являются допустимыми
Минимальное кодовое расстояние между словами, как и для всякого обычного, не помехоустойчивого кода, равно единице
Если применить для определения разрешенных кодовых комбинаций правило контроля четности, то допустимыми будут только 4 комбинации.
Минимальное кодовое расстояние с контролем по четности равно 2.

Платой за помехоустойчивость является необходимость увеличения длины слов по сравнению с обычным кодом.
В данном примере только два разряда являются информационными. Это они образуют четыре разных информационных слова.
Третий разряд является контрольным и служит только для увеличения расстояния между допустимыми словами.
В передаче информации контрольный разряд не участвует, так как является линейно зависимым от информационных.
Код с контролем по четности позволяет обнаружить нечетное количество ошибок в блоках при передаче данных, причем не указывает, сколько таких ошибок.
Четное количество ошибок (двукратные, четырехкратные и т.д.) он не обнаруживает.

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

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

Чтобы код обладал свойствами обнаруживать одиночные ошибки, необходимо ввести избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешенными комбинациями не менее двух.
В общем случае при необходимости обнаруживать ошибки кратности t0 минимальное хэммингово расстояние должно быть, по крайней мере, на единицу больше , т.е.
dmin≥t0+1
Избыточность является важной характеристикой кода, причем чрезмерное увеличение избыточности нежелательно.
Важной задачей теории информации является синтез кодов с минимальной избыточностью, обеспечивающих заданную обнаруживающую и корректирующую способность.

2. Для исправления одиночной ошибки каждой разрешенной кодовой комбинации необходимо сопоставить подмножество запрещенных кодовых комбинаций. Чтобы эти подмножества не пересекались, хэммингово расстояние должно быть не менее трех.
В общем случае исправляемые ошибки кратности tи связаны с кодовым расстоянием соотношением
dmin=2tи+1
Важно! Каждый конкретный корректирующий код не гарантирует исправления любой комбинации ошибок. Коды предназначены для исправления комбинаций ошибок, наиболее вероятных для заданного канала связи.

Для ориентировочного определения необходимой избыточности кода при заданном кодовом расстоянии d можно воспользоваться верхней граничной оценкой для r = n - k, называемой оценкой Хэмминга
Если, например, п=7, tи=1,

3. Классификация кодов
Различают коды избыточные (корректирующие) и безызбыточные.
Весом называется число единиц, содержащихся в кодовых комбинациях.
Если число единиц во всех комбинациях кода будет постоянным, то такой код будет кодом с постоянным весом.

Равномерные и неравномерные коды.
У равномерных кодов n=const, например, пятиразрядный код Бодо.
У неравномерных кодов n является переменной величиной, например, в коде Морзе кодовые комбинации имеют различную длину.
Особенность неравномерного кода состоит в том, что более длинные кодовые комбинации присваиваются знакам передаваемой информации, которые встречаются редко и наоборот, более часто встречающимся знакам присваиваются наиболее короткие кодовые комбинации.
Это обеспечивает повышение пропускной способности канала связи.
Код Морзе
Код Морзе - это способ знакового кодирования, представление букв алфавита, цифр, знаков препинания и других символов последовательностью сигналов: длинных ("тире") и коротких ("точек").
За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между элементами одного знака — одна точка, между знаками в слове — 3 точки, между словами — 7 точек.

Код Морзе статистически согласован с английским языком.
Так буква Е, которая в английском языке имеет наибольшую вероятность р(Е)=0,11, имеет самую короткую комбинацию, состоящую из одного элемента (точки).
С алфавитом русского языка код Морзе менее согласован.
Например, буква О, которая имеет наибольшую вероятность в русском языке р(О)=0,1, передаётся комбинацией из 5 элементов – – – (три тире и два разделительных интервала).
В 2004 году Международный союз электросвязи (МСЭ) ввёл в азбуку Морзе новый код для символа @ (· — — · — ·), для удобства передачи адресов электронной почты.

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

Неравномерность кода Морзе не позволяет осуществить слитную передачу кодовых комбинаций, а следовательно, и осуществить кодом Морзе автоматизированную систему связи.
Достоинством кода Морзе является его простота, облегчающая приём на слух (каждая кодовая комбинация имеет свою «мелодию»).
Телеграф и радиотелеграф первоначально использовали азбуку Морзе; позже стали применяться код Бодо и ASCII, которые более удобны для автоматизации

Код Бодо

Равномерные корректирующие коды подразделяются на блочные и непрерывные.
В блочных двоичных кодах последовательность элементарных сообщений источника разбивается на отрезки, каждый из которых независимо преобразуется в определённую последовательность (блок) кодовых символов равной длины М.
Непрерывные коды представляют непрерывную последовательность кодовых символов, её разделение на отдельные кодовые комбинации не производится.
Среди блочных кодов наиболее распространены линейные систематические коды, особенностью которых является то, что они строятся путём добавления к комбинации из «k» информационных символов «r» проверочных символов, число которых равно r = n-k.
Проверочные символы получаются путём некоторых линейных комбинаций (суммирование по модулю два) над информационными символами. Среди них наиболее изучены циклические коды.

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

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

Циклические коды относятся к блоковым кодам.
Последовательность кодовых комбинаций в циклическом коде разбивается на отдельные блоки, состоящие из информационных и проверочных разрядов и в пределах этих блоков производится исправление ошибок.
Блок состоит из:
m – информационных элементов (разрядов);
k – проверочных элементов (разрядов);
n=m+k - общее число разрядов циклического кода.
В кодовой комбинации циклического кода, как правило, в начале идут информационные элементы, а потом проверочные.
xm xm-1 … x2 x1 rk … r2 r1
4. Циклические коды

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

Цифры двоичного кода можно рассматривать как коэффициенты многочлена переменной х. Например, для кодовой комбинации 1011011 (n=7) полином
A(x)=1⃰ x6+0 ⃰ x5+1 ⃰ x4+1 ⃰ x3+0 ⃰ x2+1 ⃰ x1+1 ⃰ x0= x6+x4+x3+x+1.
При таком представлении кодов математические операции с полученными многочленами производятся в соответствии с законами обычной алгебры, за исключением того, что сложение осуществляется по модулю 2:
ха + 0 = ха, 0 + 0 = 0, ха + ха = 0
Если число разрядов кодовой комбинации n, то многочлен имеет степень (n–1).

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

Построение комбинаций циклического кода возможно путем умножения исходной комбинации А(х) на образующий полином G(x) с приведением подобных членов по модулю 2:
если старшая степень произведения не превышает (n-1), то полученный полином будет представлять кодовую комбинацию циклического кода;
если старшая степень произведения больше или равна n, то полином произведения делится на заранее выбранный полином степени n и результатом умножения считается полученный остаток от деления.
Таким образом, все полиномы, отображающие комбинации циклического кода, будут иметь степень ниже n.

В процессе кодирования сообщения:
Mногочлен А(x), отображающий двоичный код исходного передаваемого сообщения, умножается на хk.
При этом длина кодовой комбинации увеличивается на k разрядов, которые предназначены для проверочных разрядов. Эти разряды заполняются «0».
Произведение А(x)xk делят на образующий полином G(x), и остаток от этого деления R(x) суммируют с произведением А(x)xk.
Полученная кодовая комбинация, описываемая кодовым многочленом F(x)= А(x)xk+R(x), делится без остатка на образующий полином G(x).
При таком методе построения коэффициенты при высших степенях x являются обозначениями информационных разрядов, а коэффициенты при степенях порядка k-1 и ниже – проверочными.

Пример.
Дано: n=7, m=4, k=3 и G(x)=x3+x2+1.
Требуется закодировать сообщение 1 0 1 1.
Cообщению 1011 соответствует многочлен A(x)=x3+x+1.
Выполним умножение А(х) на xk, где k=3. Получим A(x)x3 = x6+x4+x3 . Разделим A(x)x3 = x6+x4+x3 на образующий полином G(x):
В итоге этой операции получим остаток R(x)=x2.
Суммируя произведение A(x)x3 с полученным остатком, получим кодовый многочлен
F(x)=A(x)x3+R(x)=x6+x4+x3+x2.
В двоичном коде этому многочлену соответствует кодовая комбинация 1 0 1 1 1 0 0, в которой проверочные разряды занимают три последние позиции.

При применении циклического кода в качестве кода с исправлением ошибок места искаженных разрядов определяются путем анализа остатка, получившегося после деления принятой кодовой комбинации на образующий полином.
Алгоритм построения кода:
По заданному объему информационного кода однозначно определяется число информационных разрядов k. Далее необходимо найти наименьшее n, обеспечивающее обнаружение или исправление ошибок заданной кратности.
Для циклического кода эта проблема сводится к нахождению образующего полинома G(x).
Образующий полином следует выбирать как можно более коротким: наибольшая степень его должна быть равна числу контрольных разрядов, а число ненулевых членов должно быть не меньше минимального кодового расстояния.
Достоинство циклического кода в том, что он используется для обнаружения как одиночных ошибок, так и групповых.

5. Код Хемминга
Ричард Хемминг разработал код, который обеспечивает обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительных проверочных бит.
Для каждого числа проверочных символов используется специальная маркировка вида (n, m),
где
n — количество символов в сообщении,
m — количество информационных символов в сообщении.
Например, существуют коды (7, 4), (15, 11), (31, 26).
Каждый проверочный символ в коде Хэмминга представляет сумму по модулю 2 некоторой последовательности данных.

Рассмотрим пример, когда количество информационных бит m в блоке равно 4. Это код (7,4), количество проверочных символов равно 3.
Классически проверочные символы располагаются на позициях, равных степеням двойки в порядке возрастания
первый проверочный бит на позиции 20 = 1;
второй проверочный бит на позиции 21 = 2;
третий проверочный бит на позиции 22 = 4.
Теперь рассчитаем значения проверочных символы по алгоритму:
k1 = m1 ⊕ m2 ⊕ m4
k2 = m1 ⊕ m3 ⊕ m4
k3 = m2 ⊕ m3 ⊕ m4
Итак, в закодированном сообщении у нас получится следующее:
k1 k2 m1 k3 m2 m3 m4
Проверочные символы можно разместить и в конце передаваемого блока данных, но тогда алгоритм для их расчета будет другим.

Построение корректирующего кода Хэмминга производится исходя из требуемого объема информационных сообщений и статистических данных о наиболее вероятных векторах ошибок в используемом канале связи.
Вектором ошибки будем называть кодовую комбинацию, имеющую единицы в разрядах, подвергшихся искажению, и нули во всех остальных разрядах.
Любую искаженную кодовую комбинацию можно рассматривать как сумму по модулю 2 разрешенной кодовой комбинации и вектора ошибки.
В коде Хэмминга необходимое число проверочных разрядов k определяется из известного соотношения
2n-k -1 ≥ n

Значения символов в проверочных разрядах устанавливаются в результате суммирования по модулю 2 значений символов в определенных информационных разрядах.
В принципе, место расположения контрольных разрядов в коде Хэмминга безразлично, но определенные удобства создает такое размещение, при котором контрольные разряды входили бы в возможно меньшее число сумм, получаемых при проверке кода.
Это будет, если контрольные разряды размещать в позициях, номера которых равны целой степени числа 2, т.е. в разрядах:
1, 2, 4, 8, 16, 32 и т.д.

Вычисление контрольных бит.
Значение каждого контрольного бита зависит от значений информационных бит, но не от всех, а только от тех, которые этот контрольный бит контролирует.
Важно: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N.
Знаком «X» обозначены те биты, которые контролирует контрольный бит. Так, бит номер 12 контролируется битами с номерами 4 и 8.
Значение контрольного бита 0 – если сумма контролируемых им бит четная, 1 – если нечетная.

Проверка на приемной стороне принятой кодовой комбинации осуществляется следующим образом: создаются контрольные суммы S1, S2, S3, S4 и т.д.
Правило построения контрольных сумм:
S1 – суммируются все нечетные разряды
S2 – суммируются начиная со 2-го разряда по два разряда подряд через 2 разряда
S3 –суммируются начиная с 4-го разряда по 4 разряда через 4 разряда
S4 – суммируются начиная с 8-го разряда по 8 разрядов через 8 разрядов.
Если все суммы равны нулю, то в принятой кодовой комбинации нет ошибки. В случае, когда одна или несколько контрольных сумм равны единице, то эти суммы располагаются слева направо в порядке возрастания индексов и полученная запись в двоичном коде указывает на номер разряда, где произошла ошибка.

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

.
Пример. Построить код Хэмминга с исправлением одиночной ошибки при 11 информационных разрядах, т.е. m=11.
Определим число контрольных разрядов (k=n – m = n-11 )
2n-m - 1= n
2n-11 – 1 ≥ 11+k
n=15
Число контрольных разрядов k= 4.
Пусть необходимо закодировать сообщение:
10110100111
Представим это информационное сообщение в виде кода Хэмминга, установив контрольные разряды на 1, 2, 4, 8 позициях.
Определим значение контрольных разрядов, запишем их в соответствующих местах, и в окончательном виде код Хэмминга без ошибок будет выглядеть так:

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

6. Коды Рида-Соломона
Коды Рида-Соломона были предложены в 1960 сотрудниками Линкольнской лаборатории МТИ Ирвином Ридом и Густавом Соломоном.
Коды Рида-Соломона базируются на блочном принципе коррекции ошибок и используются в огромном числе приложений в сфере цифровых телекоммуникаций и при построении запоминающих устройств.
Коды Рида-Соломона применяются для исправления ошибок во многих системах, включая:
- устройства памяти (включая магнитные ленты, CD, DVD, штриховые коды, и т.д.);
- беспроводные или мобильные коммуникации (включая сотовые телефоны, микроволновые каналы и т.д.);
- спутниковые коммуникации;
- цифровое телевидение / DVB (digital video broadcast);
скоростные модемы, такие как ADSL, xDSL и т.д.
Коды Рида-Соломона это недвоичные циклические коды, символы которых представляют собой s-битовые последовательности.