Теория информации и кодирования

1. Информационная модель канала связи с помехами.

Передача информации.

Структурная схема передачи информации от источника к приемнику через канал связи :

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

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

2. Принципы построения корректирующих кодов.

Теория помехоустойчивости кодирования базируется на основной теореме Шеннона.

Выводы из теоремы Шеннона:

1) При любой скорости передачи двоичных символов меньшей, чем пропускная способность

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

мала.

2) Вероятность ошибки не может быть сколь угодно малой, если скорость передачи информации

больше пропускной способности канала.

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

(бит / сек) = lim ( I / T )

T → ∞

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

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

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

Основные понятия и определения .

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

Общее количество кодовых комбинаций в коде обычно меньше, чем количество всех возможных

комбинаций из данного набора символов.

равномерные

К оды

неравномерные

В равномерных кодах все комбинации содержат одинаковое количество символов (разрядов).

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

код Морзе).

В вычислительной технике применяют в основном равномерные коды.

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

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

Пример : Пусть передаются числа от 0 до 7. Закодируем их следующим образом :

Десятичное число	Двоичное число
0 1 2 3 4 5 6 7	0000 0011 0101 0110 1001 1010 1100 1111

Как видно из таблицы, искажение хотя бы одного разряда при передаче информации переводит число в область запрещенных комбинаций. Таким образом, одиночная ошибка может быть обнаружена данным кодом. Это стало возможным из-за введения 1 дополнительного, избыточного разряда при кодировании чисел. В связи с этим, можно сказать, что из n-разрядной кодовой комбинации, только m разрядов являются информационными, а остальные k = n - m - избыточными (контрольными). Поэтому из 2 ⁿ всех возможных комбинаций допустимы только 2 ^m , а остальные ( 2 ⁿ - 2 ^m ) -запрещенные.

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

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

0010

3. Обнаруживающая и корректирующая способности кодов.

Будем считать, что любая передаваемая кодовая комбинация Bi , i = 1,2,…,N вследствие действия помех может перейти в другую кодовую комбинацию Bj , j = 1,2,…,N₀

B 1 B1

B2 B2

. .

. .

. .

BN BN₀

Общее количество переходов из разрешенной области (от источника) к приемнику Q = N * N_. Среди этих переходов можно выделить 3 варианта перехода :

1. Без искажений (количество таких переходов N = 2 ^m)

2. Каждая разрешенная комбинация может перейти в другие разрешенные N*(N-1) = 2 ^m (2 ^m -1).

Эти ошибки не могут быть обнаружены.

3. Разрешенные комбинации переходят в запрещенные и могут быть обнаружены. N*(N₀ - N)

Следовательно, обнаруживающая способность может быть определена как доля :

N*(N₀ - N) / N*N₀ = 1 – N/ N₀ = 1 – 2 ^m / 2 ⁿ = 1 – 1 / 2 ^K

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

Корректирующая способность равна отношению всех комбинаций, которые могут быть скорректированы ко всем, которые могут быть обнаружены :

(N₀ - N) / N*(N₀ - N) = 1 / N = 1 / 2 ^m

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

m = a1 = { 0,1 }. Введем дополнительные разряды а2 и а3

a1	a2	a3
1	1	0	рареш.
0 1 1	1 0 1	0 0 1	запрещ.
0	0	1	разреш.
1 0 0	0 1 0	1 1 0	запрещ.

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

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

Введем понятие вектора (последовательности) ошибок.

1011010 - искаженное слово

1001110 - неискаженное слово

0010100 - последовательность ошибок

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

Пример : Пусть код состоит из разрешенных комбинаций В1 = 001, В2 = 011, В3 = 110.

Вектор ошибок	Кодовая комбинация			Кратность ошибок Q
	В1 = 001	В2 = 011	В3 = 110
000	001	011	110	0
001 010 100	001 ( 011 ) 101	010 ( 001 ) 111	111 100 010	1
011 101 110	010 100 111	000 ( 110 ) 101	101 ( 011 ) 000	2
111	( 110 )	100	( 001 )	3

Как видно из таблицы из 21 возможной ошибки 6 не могут быть обнаружены ( они указаны в скобках ).

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

Рассмотрим варианты построения подмножеств для коррекции одиночной ошибки :

1. М1 = { 000, 101 } 2) М1 = { 000, 101 } 3) М1 = { 000, 101 }

M2 = { 010, 111 } M2 = { 010} M2 = { 111 }

M3 = { 100 } M3 = { 100, 111 } M3 = { 100, 010 }

5. Классификация кодов.

Корректирующие коды можно разделить на 2 класса :

1. Блочные (блоковые)

2. Непрерывные

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

• равномерные коды

• неравномерные коды

Блочные коды бывают:

• систематические (разделимые)

• несистематические (неразделимые)

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

Они обозначаются (n,m) , n – длина кодовой комбинации , m – информационная часть.

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

Систематические коды разделяют на :

• линейные

• нелинейные

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

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

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

6. Основные характеристики блочных кодов.

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

К основным характеристикам относится :

1) n – длина кода

2) m – информационная часть числа

3) k – контрольные разряды

4) М – основание кода ( для двоичных : 2 )

5) N = 2 ^m – мощность кода ( количество разрешенных комбинаций)

6) N₀ - общее количество всех комбинаций

7) Избыточность кода

8) W – вес кодовой комбинации

9) d min – минимальное кодовое расстояние

λ = k / n – избыточность

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

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

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

n

d ( Bi , Bj ) = ∑ ( b_i,k b_j,k )

k=1

Под минимальным кодовым расстоянием d min понимается наименьшее кодовое расстояние рассматриваемое между всеми возможными парами в коде.

1) d min >= t + 1 - для обнаружения t ошибок

2) d min >= 2t + 1 - для коррекции t ошибок

3) d min >= t + s + 1 , s < t - для обнаружения t ошибок и коррекции s ошибок

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

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

1. граница Хэмминга

(d min -1 )/ 2

k >= log ₂ ( 1 + ∑ c ⁱ_n ) , c ^m_n = n ! / m! ( n – m! )

i=1

2. граница Плоткина

k >= 2 ( d min -1 ) – log ₂ d min

3. граница Вартамова-Гильберта

(d min -1 )/ 2

k >= log ₂ ( 1 - ∑ c ⁱ_n )

i=1

Граница Хэмминга близка к оптимальной границе для кодов с большим m / n ( m / n >= 1 / 2 ) , т.е. для высокоскоростных кодов, а граница Плоткина для низкоскоростных ( m / n <= 1 / 3)

Граница Вартамова-Гильберта указывает на существование линейного облачного кода с кодовым расстоянием не менее d min и с числом контрольных разрядов не превышающим n – m.

Таким образом, границы 1 и 2 являются необходимым условием существования кода, а 3 – достаточным. Равенство в выражении 3 справедливо для совершенных кодов. Эти коды исправляют все ошибки кратности <= ( d min - 1) / 2 и не исправляют ни одной ошибки большей кратности.

Код Хэмминга – совершенный код.

8. Коды Хэмминга ( кодирование информации ).

Это я знаю

9. Коды Хэмминга ( декодирование информации ).

Это тоже знаю

10. Структурная схема кодирующего устройства ( коды Хэмминга ).

11. Структурная схема декодирующего устройства ( коды Хэмминга ).

12. Циклические коды. Принцип обнаружения ошибок.

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

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

Основное свойство циклических кодов заключается в том, что любое n – разрядное кодовое слово ( разрешенное ) A = a _{n -1} a _{n -2 …….} a ₁ a ₀ будучи циклически сдвинутым на один разряд влево

B = a _{n -2 …….} a ₁ a ₀ a _{n -1} будет принадлежать тому же самому коду.

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

Пример :

A = 10110111 B = 1101111 - впереди идущие нули не пишутся

P ( A ) = x⁷ + x⁵ + x ⁴+ x² + x + 1

P ( A ) = 1* x⁷ +0* x⁶ +1* x ⁵+ 1* x ⁴+ 0* x³ +1*x² +1* x + 1 , x⁰ = 1

P ( B ) = = x⁶ + x⁵ + x ³+ x² + x + 1

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

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

P ( x ) . Полином F*(x) , содержащий ошибку, не разделится

F(x) = G(x) x ^k R(x) , k – наивысшая степень порождающего полинома

G(x) – информационная часть

R(x) – остаток от деления

Q(x) * P(x) + R(x) = G(x) * x ^k

Q(x) * P(x) = G(x) * x ^k + R(x)

G(x) * x ^k + R(x) = F(x)

Пример : Закодируем A = 1010010 , выберем полином P(x) = x³ + x +1

F(x) = G(x) * x ^k + R(x)

G(x) = x⁶ + x⁴ + x

G(x) * x ^k = x⁹ + x⁷ + x⁴

x⁹ + x⁷ + x⁴ x³ + x +1

x⁹ + x⁷ + x⁶ x⁶ + x³ +1

x⁶ + x⁴

x⁶ + x⁴ + x³

F(x) = x⁹ + x⁷ + x⁴ + x + 1

x³

F(x)	информ.	контр.
	1010010	011

x³ + x +1

x + 1

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

Информационная часть	Контрольная часть
_ 1010010 1011__ _ 1010 1011 _ 1 1 0	000 000 011 011  x + 1

f (x) = x³ + x + 1

1 0 1 1

P₂ K узел анализа

переключатеь 1

P₂ И переключатеь 2

ТИ

P₂ И - регистр информации

P₂ K - регистр контроля (делительное устройство для нахождения остатка)

ТИ - тактовые импульсы

Кодирование : Информационная часть числа по тактовым импульсам поступает на P₂ И и сразу через переключатель 2 на выход. Одновременно информационная часть поступает на P₂K , где выполняется деление на порождающий полином, далее этот остаток через переключатель 2 подается на выход.

Декодирование : Переданное число через переключатель 1 поступает одновременно на P₂И и P₂K. В P₂И фиксируется только информационная часть, в P₂K производится деление всего числа на порождающий полином P(x). Если в результате деления получается 0, то ошибок нет. В противном случае узел анализа определяет ошибку, возникшую при передаче,

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

Выбор порождающего полинома:

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

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

1 0110111 - исходное F*(x)

10101111 - без ошибок F(x)

00011000 - последовательность ошибок E₀(x)

F*(x) = F(x) + E₀(x)

К любому числу переданному с ошибкой соответствует искаженный полином F*(x), который всегда теоретически можно представить в виде суммы по модулю 2 безошибочного полинома F(x) и полинома ошибок E₀(x). Для обнаружения ошибок F*(x) всегда должен делиться с остатком на P(x), F(x) всегда делиться на P(x) вез остатка, поэтому для выполнения этого условия E₀(x) всегда должен делиться на P(x) с остатком. Стремятся P(x) выбрать наименьшей степени.

E(x) = xⁱ , i = 1,2,3 …

P(x) = x+1

13. Структурная схема кодирующего и декодирующего устройства ( циклич. Коды ).

14. Выбор порождающего полинома в циклических кодах.

Выбор порождающего полинома

Любое искаженное кодовое слово, представленное в виде полиномаFxвсегда представить в виде суммы:Fx=FxEx, гдеFx– полином неискаженного слова,Ex– полином ошибок (в соответствующей последовательности ошибок).

Для того, чтобы циклический код мог обнаруживать ошибки, нужно выбрать такой Px, на который всегда бы делился с ненулевым остатком полиномFx, но полиномFxвсегда делился бы без остатка наPxв соответствии с формулой кодирования. Поэтому, для удовлетворения этому условию полином ошибокExвсегда должен делится наPxс остатком. Это и является основным критерием выбора порождающего полинома.

Пример: Найти полиномPx, порождающий циклический код, для обнаружения любой одиночной ошибки.

Ошибка может появится в любом разряде, тоестьEx=xi(i– номер любого разряда).

Полином выбирают, желательно наименьшей степени.

Необходимо подобрать полином с наименьшей степеньюxi, на который бы полиномEx=xiделился с остатком.Px=x1.

15. Порождающая матрица и её свойства.

Представление линейных кодов в матричном виде

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

Любой двоичный ( n , m ) код можно представить в виде матрицы, состоящей из n столбцов и 2^m - 1 строк ( -1 , т.к. нулевую комбинацию писать не принято ). Очевидно, что такая матрица для

m = 15 будет достаточно громоздкой.

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

Пусть разрешенная кодовая комбинация а₁ а₂ а₃ ..… а_m e₁ e ₂ e _{3 …..} e _k

информационная контрольная

e_i = α _{i 1} α ₁ + α _{i 2} α ₂ + …. + α _{i m} α _m , где α _{i 1} , α _{i 2} , …… , α _{i m} или 0 или 1

Базовые комбинации линейного кода удовлетворяют следующим свойствам :

1 ) Они должны быть различны и не включать нулевую комбинацию

2 ) Они должны быть линейно независимыми

3 ) Количество единиц в каждой из них должно быть не менее d min

4 ) Минимальное кодовое расстояние должно соответствовать заданному

Построенная из базовых комбинаций матрица называется порождающей ( образующей ). Она состоит из n столбцов и m строк , записывается M n x m . Порождающая матрица выглядит следующим образом :

а₁₁ а₁₂ ..… а_m e₁₁ e_{12 …..} e _k

M n x m = а₂₁ а₂₂ ..… а_m e₂₁ e_{22 …..} e _k

………………………………..

a_m1 а_m2 ..… а_m e_m1 e_{m2 …..} e _mk

информационная проверочная С k x m

Для информационной части матрицы базовые комбинации удобно представлять в виде единичной матрицы E_m n x m

10 … 0

M n x m = 01 … 0

………

00 … 1

Если в качестве информационной части выбрана единичная матрица, то очевидно проверочная матрица С k x m должна быть построена исходя из следующих условий :

1 ) Количество единиц в матрице С k x m должно быть не меньше d min – 1

2 ) Минимальное кодовое расстояние в С k x m должно быть не менее d min – 2

Таким образом порождающая матрица имеет вид

1000 ..… 0 e₁₁ e_{12 …..} e _k

M n x m = 0100 ..… 0 e₂₁ e_{22 …..} e _k

………………………………

0000 ..… 1 e_m1 e_{m2 …..} e _mk

Пример : Используя для расчета k границу Хэмминга построить порождающую матрицу для кода способного исправлять одиночную ошибку ( t = 1 ) при передаче N =16 сообщений

для N=16 m = 4 N = 2^m (d min -1 )/ 2

граница Хэмминга k >= log ₂ ( 1 + ∑ c ⁱ_n )

i=1

для обнаружения t ошибок d min >= t + 1

для исправления t ошибок d min >= 2 t + 1

У нас d min >= 2*1 +1 = 3

1

k >= log ₂ ( 1 + ∑ c ¹_n ) , k >= log ₂ ( 1 + n ) , k = 3

1

1000 101 1000 111

M _7,4 = 0100 011 или 0100 110 или и т.д.

0010 110 0010 011

0001 111 0001 101

Алгоритм образования значений контрольных разрядов кодовой комбинации по информационной части с помощью матрицы M n x m выглядит так :

e₁ = e₁₁ а₁ + e₂₁ а₂ + _…..+ e _m1 а_m

e₂ = e₁₂ а₁ + e₂₂ а₂ + _…..+ e _m2 а_m

………………………………………

e_k = e_1k а₁ + e_2k а₂ + _…..+ e _mk а_m

16. Проверочная матрица и её свойства.

Гораздо удобнее проверочные уравнения выполнить с помощью матрицы , состоящей из k строк и m столбцов. Получим ее : сначала строится единичная матрица Е k,k . К ней приписывается D m,k , содержащая m столбцов и k строк, причем каждая ее строка соответствует столбцу контрольных разрядов подматрицы С k,m , порождающей матрицы, другими словами D k,m является транспонированной по отношению к С k,m.

e₁₁ e_{21 …..} e_m1 100 ……0

H n x k = [D m,k ; E_k ] e₁₂ e_{22 …..} e_m2 010 …….0

………………………………

e_1k e_{2k …..} e_mk 000 ..… 1

С помощью этой матрицы операция кодирования осуществляется очень просто : позиции занимаемые единицами в i – ой строке подматрицы D m,k определяют те информационные разряды, которые должны участвовать в формировании контрольного разряда

Пример : Построить проверочную матрицу H кода 7,4 , порождающая матрица которого имеет вид :

1000 111 1110 1110100

M _7,4 = 0100 110 D _4,3 = 1101 H _7,3 = 1101010

0010 101 1011 1011001

0001 011

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

e₁ = a₁ + a₂ + a₃

e₂ = a₁ + a₂ + a₄

e₃ = a₁ + a₃ + a₄

Закодируем 1 0 1 0 0 1 0

a₁ a₂ a₃ a₄ e₁ e₂ e₃

На основании матричного представления кодов можно сделать следующие выводы :

1. С помощью порождающей матрицы M _{m x n} можно представить весь набор кодовых комбинаций в удобной и компактной форме и довольно просто провести операцию кодирования.

2. Проверочную матрицу H _{m x k} обычно используют при построении кодирующих и декодирующих устройств, т.к. она определяет алгоритм нахождения проверочных разрядов по информационным значениям. Кроме того данная очень удобна для указания места отсечки в кодовой комбинации

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

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

Обычно при декодировании информации используются проверочные соотношения полученные по проверочной матрице H _{m x k} . При этом вычисляется синдром (контрольное число). Синдром рассчитывается как сумма по модулю 2 принятых контрольных разрядов и контрольных разрядов, вычисленных по принятым информационным. Характерной особенностью синдрома является то, что он независим от передаваемой кодовой комбинации, а зависит только от характера ошибок.

Пример : Задана проверочная матрица H _{7 x 3}

0 1 1 1 1 0 0 S₁ = e₁ + e₁ ^/

H _7,3 = 1 0 1 1 0 1 0 S₂ = e₂ + e₂ ^/

1 1 0 1 0 0 1 S₂ = e₃ + e₃ ^/

a₁ a₂ a₃ a₄ e₁ e₂ e₃

e₁ ^/ - контрольный разряд, вычисленный по принятым информационным

e₁ ^/ = a₂ + a₃ + a₄

e₂ ^/ = a₁ + a₃ + a₄

e₃ ^/ = a₁ + a₂ + a₄

Возьмем А = 1 0 1 1 0 1 0

a₁ a₂ a₃ a₄ e₁ e₂ e₃

Пришедшее число 1 0 1 1 1 1 0

a₁ a₂ a₃ a₄ e₁ e₂ e₃

S₁ = 1+0 = 1 0111 100

S₂ = 1+1 = 0 1011 010

S₃ = 0+0 = 0 S = 1 0 0 1101 001

(в этом разряде ошибка)

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

Составим последовательность ошибок 1000 000

S₁ = 0+0 = 0

S₂ = 0+1 = 1

S₃ = 0+1 = 1

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

2^k >= n-1

2^k+1 >= n

k >= C_n¹

Для исправления одиночных и двоичных ошибок 2^k + 1>= C_n¹ + C_n²

Для всех разрядов 2^k + 1>= C_n¹ + C_n² + …. + C_n^e

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

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

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

Инверсный код

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

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

10111 10111

11001 00110

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

В этом коде не обнаруживаются попарные ошибки 2, 4 , 6 .... кратности

18. Представление кодов Хэмминга в матричном виде.

Представление кода Хэмминга в матричном виде

Характерной особенностью кода Хэмминга с d min >= 3 является то, что в его проверочной матрице используются все комбинации , кроме нулевой

000000011111111

H _7,3 = 000111100001111

011001100110011

101010101010101

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0

H _15,4 = 0 1 1 1 0 0 0 1 1 1 1 0 1 0 0

1 0 1 1 0 1 1 0 0 1 1 0 0 1 0

1 1 0 1 1 0 1 0 1 0 1 0 0 0 1

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

e₁ = a₁₅ + a₁₄ + a₁₂ + a₁₁ + a₉ + a₇ + a₅

e₂ = a₁₅ + a₁₃ + a₁₂ + a₁₀ + a₉ + a₆ + a₅

e₃ = a₁₄ + a₁₃ + a₁₂ + a₈ + a₇ + a₆ + a₅ a₆ a₅ - ошибка

e₄ = a₁₁ + a₁₀ + a₉ + a₈ + a₇ + a₆ + a₅ S = 0111 S = 1111

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

7 6 5 4 3 2 1

1 1 1 1 0 0 0

H _15,4 = 1 1 1 0 1 0 0

0 1 1 0 0 1 0

1 0 1 0 0 0 1

a₄ a₃ a₂ e₃ a₁ e₂ e₁

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

A = 1101

e₁ = a₄ + a₃ + a₂

e₂ = a₄ + a₃ + a₁

e₃ = a₄ + a₂ + a₁

Закодированное число : 1100110

Ошибка в разряде a₂

a₄ a₃ a₂ e₃ a₁ e₂ e₁

1 1 1 0 1 1 1

S₁ = 0+1 = 1

S₂ = 1+1 = 0

S₃ = 0+1 = 1 S = 101

19. Матричная запись циклического кода.

Матричная запись циклических кодов

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

Проверочная матрица С _k,m строится наиболее удобно следующими двумя способами :

1) Каждая строка матрицы E_m^Т , предварительно умноженная на x^k , делится на порождающий полином P(x) и полученный остаток R(x) является строкой матрицы С _k,m . Деление производится по формуле :

G (x) * x^k

→ R(x)

P(x)

Пример : Построить порождающую матрицу M(7,4) , P(x) = х³ + х +1

0010 011

E ₄^Т = 0010 С _3,4 = 110

0100 111

1000 101

G (x) * x^k 1* х³

1 . = = х +1 → 011

P(x) х³ + х +1

G (x) * x^k х * х³

2 . = = х² +х → 110

P(x) х³ + х +1

G (x) * x^k х² * х³

3 . = = х³ + х +1 → 111

P(x) х³ + х +1

G (x) * x^k х³ * х³

4 . = = х² +1 → 101

P(x) х³ + х +1

Проверочную матрицу С _k,m можно построить по другому. Для этого !!!!!!!!!!!!!!!!

при этом получающиеся !!!!!!!!!!!!!!!! ,то последующая строка матрицы С _k,m получается путем циклического сдвига влево на 1 разряд предыдущей строки. Этот сдвиг продолжается до тех пор пока степень остатка не станет равной n-m-1

1000 000

1 011

011

1100 С _k,m = ₁₁₀

1011 111

1110 101

1011

101

20. Итеративные коды. Блочный итеративный код с проверкой на четность строк и столбцов.

Итеративные коды

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

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

1) Блочный итеративный код с проверкой на четность строк и столбцов.

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

а₁₁ а₁₂ …… а_{1i …….}a_1n-1 a_1n

а₂₁ а₂₂ …… а_2i ….. ..a_2n-1 a_2n

………..………………………..

а_j1 а_j2 …… .. а_{ji ……..}a_jn-1 a_jn

………..………………………..

а_l-1,1 а_l-1,2 …..а_{l-1,i ….}a_l-1,1n-1 a_l-1,n

а _l,1 а_l,2 …….а_{l,i ……….}a_l,n-1 a_l,n

n-1

a_jn = ∑ а_ji mod 2

i=1

l-1

а_l,i = ∑ а_ji mod 2

i=1

l-1

a_l,n = ∑ a_jn mod 2

j=1

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

Таким образом, данный код гарантированно корректирует одиночные ошибки и обнаруживает двоичные.

21. Итеративные коды с проверкой на четность слов и диагоналей. Непрерывный двумерный код.

Интерактивный код с проверкой на четность слов и диагоналей

Непрерывный двумерный код

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

.

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

m

a_m+1,k+j = ∑ а_i,k+j ( mod 2 )

i=1

m+2

a_m+2,k+m+2 = ∑ а_i,k+i ( mod 2 ) , где а_i , k_i - информационные разряды

i=1

Как видно из рисунка все групповые ошибки, находящиеся вдоль одной дорожки могут быть скорректированы, т.к. каждому групповому искажению будет присуще своё индивидуальное нарушение четности в m + 1 и m + 2 дорожке. В m + 1 контрольную дорожку добавляется дополнение до четности вдоль столбца, а в m + 2 разряд дополнение до четности по диагонали. Лишь часть искаженных информационных разрядов попавших внутрь треугольника, образованного первым столбцом с искаженными разрядами, диагональю, проходящей через первый контрольный разряд и контрольной дорожкой

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

Кодирующее устройство состоит из входного регистра, схемы свертки по модулю 2 для формирования контрольных значений по столбцу ( блок СС ), схем формирования контрольных разрядов по диагонали, включающих n сумматоров по модулю 2 ( блоки m2 ), m ячеек памяти ( П ) и выходного регистра.

Подлежащая кодированию информация поступает с входного регистра на выходной, схема свертки CC формирует дополнение до четности m-разрядного слова по столбцу и результат записывает в m + 1 разряд выходного регистра. Нижняя часть схемы формирует дополнение до четности по диагонали, на первый вход сумматора m2 подается текущий разряд, например, второй, а на второй вход m2 подается разряд предыдущей строки сдвинутой на 1 разряд. Результат записывается в m + 2 выходного регистра.

22. Итеративные коды с проверкой на четность слов и диагоналей. Блочные двумерные коды.