Презентация на тему Помехоустойчивое кодирование

физическая, статистическая, )
Коды, позволяющие обнаруживать и исправлять ошибки бывают

двух видов: - блоковые коды; - сверточные коды

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

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

Длина слова систематического кода (n) = число информационных разрядов (m) + число контрольных разрядов(k)

m

k = n-m

n

первичный сигнал
Декодированный сигнал
помеха
Схема системы связи
Сообщение: α = ai1 ai2

… aim ,
где aij ∈Σ

Алфавит: Σ = {a1,a2,…, an}
Σ’ = {b1,b2,…, bp}

Закодированное сообщение: β = c(ai1) c(ai2) … c(aim) = bi1 bi2 … bin

Схема работы кодирующего и декодирующего устройств

Процесс кодирования

Процесс декодирования

вектор в пространстве или точка в пространстве Bn, где

n – длина слова ( блока); B={0,1}.
Всего точек в пространстве Bn → 2n.

Пример пространства B3

Код – это некоторые точки пространства Bn, или некоторое подмножество пространства Bn

Пример пространства B2

00

01

10

10

Пример пространства B1

0

1

Примеры пространств Bn разных размерностей

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

символов. На выходе ей соответствует последовательность из n двоичных символов, причем n>k.

2. Всего может быть:
2k различных входных и
2n различных выходных последовательностей.

3. Из общего числа 2n выходных последовательностей только 2k последовательностей соответствуют входным. Их называют разрешенными кодовыми комбинациями.

4. Остальные 2n-2k возможных выходных последовательностей для передачи не используются. Их называют запрещенными кодовыми комбинациями.

следующие варианты передачи и получения сообщений:
Передача с ошибкой,

ошибка обнаружена (отправили αi → получили αj , ∀ i,j=1..p, i≠j);
Передача без ошибок (отправили αi → получили αi , ∀ i=1..p);
Передача с ошибкой, ошибка не обнаружена (отправили αi → получили β , ∀ i=1..p, β - не является кодовым словом);

α1
α2
…
αp

Канал связи

α1
α2
…
αp

Передача сообщений

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

Определение. Код обнаруживает t ошибок, если для всякого r ≤ t r ошибок переводит кодовое слово в некодовое.

дополняется 1 контрольным разрядом, в который записывается 0 или

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

ai1 ai2 … aim

(ai1 ⊕ ai2 ⊕ … ⊕ aim)

+

+

Пример кодирования двухразрядных слов:

00 → 000
01 → 011
10 → 101
11 → 110

Код -тетраэдр

Примеры
кодов

тому, что появляется возможность не только обнаружить, но и

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

Модификация кода с проверкой на четность

 

Это (n, 1)-код. Для него минимальное расстояние равно n,

и при предположении, что большинство принятых битов совпадает с переданным информационным битом, может быть исправ­лено (n — 1)/2 ошибок.

Коды с повторением

– расстоянием Хэмминга - между двумя словами a и

b называют число несовпадающих позиций этих слов.
Например: расстояние между словами a=0110100 и b=0010101 равно 2.

Определение: Минимальное расстояние, взятое по всем парам кодовых разрешенных комбинаций кода, называют (минимальным) кодовым расстоянием (d0min).

Расстояние Хэмминга. Кодовое расстояние

0110100
0010101
0100001

⊕

Пример: Рассмотрим код, заданный таблицей

d(10101, 10010) = 3
d(10101, 01110) = 4
d(10101, 11111) = 2
d(10010, 01110) = 3
d(10010, 11111) = 3
d(01110, 11111) = 2

d0min = 2 – кодовое расстояние для данного кода

кодовую комбинацию, отличающуюся от данной в наименьшем числе символов.

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

Для каждой вершины куба имеются три вершины, которые отстоят от нее на один шаг (на расстоянии одного ребра куба), еще три вершины, которые отстоят на два шага, и одна вершина — на три шага.

Расстояние между ближайшими кодовыми комбинациями называется кодовым расстоянием.

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

Геометрическая интерпретация кодового расстояния и расстояния Хэмминга

(избыточность в коде отсутствует), то не могут быть обнаружены

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

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

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

101. Для исправления одиночной ошибки расстояние от точки 0

следует увеличить еще на один шаг. Такая комбинация будет только одна — 111.

Для трехмерного куба корректирующие комбинации расположены на противоположных вершинах куба. Это пары 000—111, 010—101, 001—110, 011—100 (Коды-спутники).

чтобы при искажении любой комбинации не могла быть образована

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

Например, если передавать буквы алфавита, которым соответствуют следующие комбинации двоичного кода: А — 00000, Б — 00111 и В — 11100, то при искажении любого одного знака легко определить, какая комбинация была передана, так как каждая из них отличается друг от друга не меньше чем в трех символах (кодовое расстояние d≥3).

Исправление ошибки в кодах-спутниках

до r включительно минимальное хэммингово расстояние между разрешенными кодовыми

комбинациями должно быть по крайней мере на единицу больше r.

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

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

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

d0 min≥r+1

кодовых слов есть 000, 101, 011, 110. Минимальное расстояние

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

Общее выражение для определения кодового расстояния в случае одновременного обнаружения и исправления ошибок
d = r + s + 1
, где
r — число обнаруживаемых ошибок;
s — число исправляемых ошибок;
d — минимальное количество элементов, в которых одна кодовая комбинация отличается от другой.

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

d = 2s + 1

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

которые входит значение ошибочного разряда.

Примеры кодов

Для ∀m ∃ (2m-1, 2m-1-m) код Хэмминга

k - разрядное двоичное число

Это систематический код, с m информационными и k = (n-m) проверочными битам. Код Хэмминга является кодом с проверкой на четность, с той лишь разницей, что эта проверка производится k раз.
При каждой проверке охватывается часть информационных символов и один избыточный, при этом получается один контрольный символ.
Если результат проверки дает четное число, то контрольному символу присваивается значение ‘0’, если нечетное – ‘1’.

 

 

кодовой комбинации, при которой каждый из них включается в

минимальное число проверяемых групп (лучше в одну).

Порядок проведения кодирования и проверок

s1 = u1⊕u3⊕u5⊕u7⊕u9⊕u11 ⊕ …
s2 = u2⊕u3⊕u6⊕u7⊕u10⊕u11⊕…
s3 = u4⊕u5⊕u6⊕u7⊕u12⊕u13⊕…
s4 = u8⊕u9⊕u10⊕u11⊕u12⊕u13⊕…

Позиции контрольных битов

все биты чётности верны, то перейти к п 5.
Вычислить

сумму номеров всех неправильных битов чётности
Инвертировать содержимое бита, номер которого равен сумме, найденной в п.3
Исключить биты чётности , передать правильный информационный код

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

числом информационных разрядов nи и числом корректирующих разрядов nк

должно удовлетворять следующим условиям:

При этом подразумевается, что общая длина кодовой комбинации n=m+k

Для практических расчетов при определении числа контрольных разрядов кодов с минимальным кодовым расстоянием d0min = 3 удобно пользоваться выражениями:
Если известна длина полной кодовой комбинации n

 

 

 

2. Если при расчетах удобнее исходить из заданного числа информационных символов m

 

При построении кодов перед разработчиками стоит задача определения числа добавочных, корректирующих символов k, или исходя из числа информационных разрядов m, либо из общей длины кода n.

= 4)
 
 
Для кодов длиной в n символов, исправляющих одну

или две ошибки (d0min = 5),

 

Для практических расчетов можно пользоваться выражением

 

Для кодов, исправляющих три ошибки (d0min = 7),