Закодируйте сообщениеα кодом Хемминга из задачи 4.4.4

 

а) α =(0011)	б) α =(1011)	в) α =(0111)	г) α =(0001)	д) α =(0010)
е) α =(1010)	ж) α =(0110)	з) α =(1001)	и) α =(1000)	к) α =(1100)

Образец: Закодируйте сообщение α =(0101 ) кодом Хемминга из задачи 4.4.4. (образец):

Решение: Умножим кодовое слово a на порождающую матрицу G:

 

.

Отсюда кодированное сообщение имеет вид (0101011).

Первые m =4 информационные символы вектора αG образуют исходное сообщение α =(0101), последние n-m =3символа используются для контроля.

 

4.4.6. Решите задачу:

Декодируйте кодом Хемминга сообщение b в задаче 4.4.3.:

а) b =(1100110)	б) b =(1010111)	в) b =(1111110)	г) b =(0100011)	д) b =(1101101)
е) b =(1110110)	ж) b =(1001101)	з) b =(0010010)	и) b =(1110111)	к) b =(1010001)

 

Образец: Декодируйте кодом Хемминга сообщение b =(0111001) в задаче 4.4.3.

Решение: Умножим проверочную матрицу из задачи 4.30 на вектор-столбец = – транспонированное сообщение b. Имеем

.

Т.к. в результате получен ненулевой вектор , то это означает, что при декодировании была допущена ошибка. Т.к. этот вектор-столбец совпадает с первым столбцом проверочной матрицы M, то надо изменить, (инвертировать) именно первый символ в сообщении b. Получим новый вектор b_н= (1111001), в котором при m =4 первые четыре буквы a =(1111) составляют истинное декодированное сообщение.

4.4.7. Построить коды H(b) для заданных слов b =(010101), x=(110100), y=(011010).

Решение.

1) Для построения кодов H(b) необходимо иметь двоичные векторы, записанные словом длиной k. Рассчитаем по k формуле . При n = 6 имеем неравенство . Отсюда т.к. 4<6<8, то 2²<6<2³. Значит k =3.

2) Двоичные векторы длины 3 обозначим e₃:

n
e 3(n)	e 3(1)	e 3(2)	e 3(3)	e 3(4)	e 3(5)	e 3(6)
Код

 

2) Т.к. число b =(010101) содержит знаки 1 в четных разрядах, то для записи H(b) в векторной форме нам понадобятся только те векторы e₃, которые имеют четные номера. Отсюда имеем

H(b)= (0,1,0) Å (1,0,0) Å (1,1,0)=(0,0,0).

Для слова x=(110100) значащие разряды первый, второй и четвертый, поэтому

H(x)= (0,0,1) Å (0,1,0) Å (1,1,0)=(1,1,1).

Для слова y=(011010) значащие разряды второй, третий и пятый, поэтому

H(y)= (0,1,0) Å (0,1,1) Å (1,0,1)=(1,1,0).

Согласно теореме, bÎ H 6, .

4.4.8. Решите задачу. В двоичном слове b в задаче 4.4.6. произошла замена одного из символов. С помощью векторной формы кода Хемминга найдите и исправьте ошибку.

Образец: Пусть в слове b =(110101) произошла замена одного из символов, например, первого. Новое слово А=(1 10101). Докажите с помощью векторной формы кода Хемминга, что заменен именно первый символ.

Решение: Найдем H(A)=(0,0,1) Å (0,1,0) Å (1,0,0) Å (1,1,0)=(0,0,1), что соответствует числу 1. Т.к. Полученный кортеж (001) есть двоичная форма числа 1, то первый разряд есть номер замещенного места.

4.4.9. Решите задачу:

Закодируйте слово длины 4 с помощью кода с проверкой четности.

а) α =(0011)	б) α =(1011)	в) α =(0111)	г) α =(0001)	д) α =(0010)
е) α =(1010)	ж) α =(0110)	з) α =(1001)	и) α =(1000)	к) α =(1100)

 

Образец: Закодируйте слово α =(0101) длины 4 с помощью кода с проверкой четности.

Решение: Найдем сумму по модулю 2 всех двоичных букв этого слова. Имеем:

, поэтому передано будет сообщение в виде слова b =(01010) длины 5.

4.4.10. Решите задачу:

Декодируйте слово длины 5 с помощью кода с проверкой четности

а) b =(00110)	б) b =(10111)	в) b =(01110)	г) b =(00011)	д) b =(00101)
е) b =(10100)	ж) b =(01100)	з) b =(10010)	и) b =(10001)	к) b =(11001)

Образец: Декодируйте слово b =(01110) длины 5 с помощью кода с проверкой четности.

Решение: Отбросив последнюю букву передаваемого слова, имеем слово α =(0101) длины 4, которое передавалось по каналу связи (в задании 4.4.9).

4.4.11. Решите задачу:

Определите, допущены ли ошибки в сообщении, заданном в задании 4.4.10.

Образец: Определите, допущены ли ошибки в сообщениях a ₁=(01110) и a ₂= (01010).

Решение: Для обнаружения ошибки, проверим с помощью М2 сумму всех букв закодированного слова в полученных сообщениях: a ₁= . Т.к. сумма всех букв закодированного слова оказалась равной 1, то при его передаче по каналу связи была допущена ошибка.

Для второго сообщения имеем a ₁= . Т.к. сумма всех букв закодированного слова оказалась равной 0, то при его передаче по каналу связи код с проверкой четности не позволяет выявить ошибку.

4.4.12. Для заданного сообщения А построить код Хемминга B. Необходимо обнаружить и справить одиночную ошибку, если при хранении информации она приобрела вид:

а) 1011010	б) 1001000	в) 1011100	г) 0011000	д) 1010000
е) 1111000	ж) 1011001	з) 10110000	и) 010110	к) 101010

Образец: Для заданного сообщения A =101100 построить код Хемминга B.

Решение: Кодируемое слово A =101100 длины m =6.

1) Рассчитаем k по формуле . При m = 6 имеем неравенство . Отсюда т.к. 4<6<8, то 2²<6<2³. Значит k =3 и закодированное слово должно быть длиной m+ k =6+3=9. Значит, код содержит 6 информационных и 3 проверочных символа, расположенных на местах, соответствующих разрядам, равным целым степеням числа 2. Тогда проверочные символы расположены на 2 ^k местах: т.е. занимать 2⁰=1, 2¹=2, 2²=4, разряды. Остальные разряды двоичного числа заняты информационными символами.

2) Обозначим через p_i символы, расположенные на проверочных i –ых разрядах. Тогда код В должен иметь вид двоичного числа, в котором на 1-м, 2-м и 4-м месте расположены проверочные символы p _1, p ₂, p ₄, а на остальных местах разместим информационные символы, взятые из заданного числа A = 101100. Тогда код В примет вид:

p ₁ p ₂ 1 p ₄ 01100

3) Для вычисления проверочных символов составим таблицу:

i	i в двоичном представлении	Информац. позиции	Расчет проверочных символов	Провероч. позиции	Сообщение после кодирования	Номер строк, формирующих провер.символ
	0001		p 3Å p 7			3 и 7
			p 3Å p 6Å p 7			3, 6 и 7
	0011
			p 6Å p 7			6 и 7
	0110
	0111

Для вычисления проверочных символов будем учитывать, что p_i равно сумме по модулю 2 тех информационных символов, номера которых имеют единицу в двоичном представлении в i –ых разрядах, считая справа налево: p ₁ – в первом разряде справа, p ₂ – во втором разряде, p ₄ – в третьем разряде справа. Т.к. информационные позиции для единиц в первом разряде, расположенных на 3-м и 7-м местах, то p ₁ = p ₃Å p ₇=1 Å 1=0.

Т.к. информационные позиции для единиц во втором разряде, расположены на 3-м, 6-м и 7-м местах, то p ₂ = p ₃Å p ₆Å p ₇=1 Å 1Å 1=1.

Т.к. информационные позиции для единиц в третьем разряде справа расположены на 6-м и 7-м местах, то p ₄ = p ₆Å p ₇=1Å 1=0.

4) Объединим информационные и проверочные символы. Тогда закодированное кодом Хемминга сообщение имеет вид: В=011001100.

5) Проверим правильность построенного кода. Для этого найдем значение H(B). Для этого выпишем столбец, составив его из двоичных номеров строк, в которых знак кода В равен 1, т.е. 2-ю,3-ю,6-ю и 7-ю строки. Если сумма М2 номеров в каждом разряде равна 0, то код составлен без ошибок:

Номер строки	Двоичное представление номера строки	Знак сообщения В
	0011
	0110
	0111
Сумма разрядов М2

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

4.4.13. В построенный в задании 4.4.12. код Хемминга внести одиночную ошибку. Необходимо обнаружить и справить эту одиночную ошибку в коде Хемминга B.

Образец. В образце задания 4.4.12. сообщение, закодированное кодом Хемминга, имеет вид: В=011001100. Пусть при передаче сообщения произошла замена символа в пятом разряде. Необходимо обнаружить и справить эту одиночную ошибку в коде Хемминга B.

Решение. Новое сообщение имеет вид В*=0110 1 1100.

1) Для обнаружения ошибки, найдем значение H(B*). Для этого выпишем в столбец двоичные номера строк, в которых знак сообщения В* равен 1. Найдем сумму М2 знаков номеров в каждом из разрядов.

i	Д воичное представление номера строки	Сообщение после его передачи
	0001

 

i	Д воичное представление номера строки	Сообщение после его передачи

Полученное число 0101 есть двоичная форма десятичного числа 5: 0101₂=5₁₀. Это означает, что именно в пятом разряде сообщения В*=0110 1 1100 произошла замена символа. Чтобы исправить ошибку, заменим символ 1 в пятом разряде на символ 0. Действительно, сообщение имело вид: В=0110 0 1100.