Задача №3.

Задан ряд из четырёх десятичных чисел.

1)Представить каждое число с помощью 6 символов равномерного двоичного кода.

2)Закодировать полученную последовательность двоичных символов кодом Лемпеля-Зива.

3)Произвести декодирование.

Исходные данные :

N	числа
22	45	58	39	28

1) Представление чисел с помощью шести символов равномерного двоичного кода :

45=101101 ;

58=111010 ;

39=100111 ;

28=011100 .

2) Закодируем кодом Лемпеля-Зива :

3)Произведём декодирование :

Глава 3. Расчётное задание № 3.

Задание №1

Строки производящей матрицы линейного блочного (n,3)-кода – это три n-разрядные комбинаций (младший разряд – справа), которые в двоичной форме представляют десятичные числа g₀, g₁, g₂. Найти: кодовое расстояние d_код, максимальные кратности гарантированно обнаруживаемых q_o и исправляемых q_и ошибок. Закодировать двоичную комбинацию, соответствующую десятичному числу in, и двоичную комбинацию на выходе кодера представить в форме десятичного числа out.

(Примечание: верхняя строка производящей матрицы g₀ соответствует младшему разряду комбинации на входе кодера.)

Исходные данные:

N	n	in	g0	g1	g2
22	10	6	361	682	911

Переведем заданные числа g₀, g₁, g₂ в двоичную систему счисления:

361₁₀=101101001₂ ;

682₁₀=1010101010₂ ;

911₁₀=1110001111_{2 .}

Затем запишем построчно производящую матрицу :

Для нахождения d_код запишем матрицу расстояний D:

Значению d_код соответствует значение наименьшего из недиагональных элементов матрицы D:

(1.1)

В соответствии с неравенствами для максимальной кратности гарантированно обнаруживаемых q_o и исправляемых q_и ошибок:

(1.2)

(1.3)

Определим их значения:

Вектор, соответствующий кодируемому числу in=1, имеет вид:

.

Для получения кодовой комбинации out, соответствующей вектору , необходимо произвести следующую операцию:

=*=*==911 .

Кодовая комбинация :

.

Таблица ответов для проверки:

N=22

dкод	qo	qи	out	S
4	3	1	911	919

Задание №2

Двоичные комбинации, соответствующие пяти десятичным числам (n, in, g₀, g₁, g₂) из задания 5, считать строками проверочной матрицы H кода (n,n-5).

Определить:

способен ли этот код обнаружить любую однократную ошибку

(d=1, если способен, d=0 в противном случае);

способен ли этот код исправить любую однократную ошибку

(c=1, если способен, c=0 в противном случае).

По данным предыдущей задачи запишем построчно проверочную матрицу H , где строки соответствуют десятичным числам n, in, g₀, g₁, g₂ :

.

Транспонированная матрица H^T принимает вид:

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

Принятый вектор b в случае наличия только однократных ошибок представляет собой сумму по модулю 2 (mod2) передаваемого вектора a и вектора e – однократной ошибки.

(2.1)

Если умножить обе части вышеприведенного равенства на H^T, при условии получим:

(2.2)

Если ошибка, есть, то значение синдрома c0, в противном случае b=a, c=0, т.е. ошибки не было.

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

=

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

Таблица ответов для проверки:

d	c	S
0	0	0