Р е ш е н и е

В соответствии с равенствами (2.16) вычислим значение синдрома С и выполним общую проверку на четность (вычислим значение V) первого кодового слова Cod 1=00011001:

Получили нулевое значение синдрома С=(с₃с₂с₁)=0 и значение V=1, следовательно, произошла ошибка в восьмом разряде. На передающем конце было отправлено кодовое слово

Cod 1
Вектор ошибки а8
Верная комбинация

Те же действия выполним для второго кодового слова

Cod 2=10111101:

Получили ненулевое значение синдрома С=(с₃с₂с₁)=101 и значение V=0, следовательно, произошла двойная ошибка.

В соответствии с равенствами (2.16) вычислим значения синдрома С и выполним общую проверку на четность третьего кодового слова Cod 3=10111001:

Получили ненулевое значение синдрома С=(с₃с₂с₁)=(110)₂=6₁₀ и значение V=1, следовательно, произошла одиночная ошибка в шестом разряде.

На передающем конце было отправлено кодовое слово

Cod 3
Вектор ошибки а6
Верная комбинация

Ответ:

При передаче первого кодового слова Cod 1=00011001 произошла ошибка в восьмом разряде.

При передаче второго кодового слова Cod 2=10111101 произошла двойная ошибка, в связи с чем необходимо послать запрос на повторную передачу этого кодового слова.

При передаче третьего кодового слова Cod 3=10111001 произошла одиночная ошибка в шестом разряде.

В первом и третьем случаях верное кодовое слово – 10011001.

З а м е ч а н и е: Убедитесь, что при передаче кодового слова 10011001 могла произойти двойная ошибка, приведшая к приему второго кодового слова Cod 2=10111101.

3. Список задач

3.1. Чему равны значность и вес каждой из следующих комбинаций:

a) 00100101; b) 01001; c) 0000000; d) 101; e) 0001010;

f) 11011010; g) 10110; h) 111111; j) 010; k) 1110101.

3.2. Определить минимальное кодовое расстояние, необходимое для обнаружения в коде ошибки кратности

a) два;

b) три;

c) четыре;

d) пять.

3.3. Определить минимальное кодовое расстояние, необходимое для исправления в коде ошибки кратности

a) два;

b) три;

c) четыре;

d) пять.

3.4. Определить минимальное кодовое расстояние, необходимое для кода, обладающего следующими корректирующими способностями:

а) обнаружения ошибок кратности два и исправления одиночных ошибок;

b) обнаружения ошибок кратности три и исправления одиночных ошибок;

c) обнаружения ошибок кратности три и исправления двойных ошибок;

d) обнаружения ошибок кратности четыре и исправления одиночных ошибок;

e) обнаружения ошибок кратности пять и исправления тройных ошибок.

3.5. Код состоит из четырех кодовых слов: 11110, 00011, 01001, 10001. Способен ли данный код обнаружить одиночную ошибку?

3.6. Код состоит из четырех кодовых слов: 11110, 10001, 01111, 00101. Способен ли данный код исправить одиночную ошибку?

3.7. Построить четырехзначный двоичный код, обнаруживающий одиночную ошибку.

3.8. Определить количество проверочных разрядов (n-k) для построения систематического кода, исправляющего одиночную ошибку и содержащего k=5 информационных разрядов.

3.9. Определить максимальное количество информационных разрядов k систематического кода, исправляющего одиночную ошибку, если допустимая длина всего кода n=10 символов.

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

3.11. Определить количество корректирующих разрядов (n-k) для построения кода, обнаруживающего все трехкратные ошибки, если допустимая длина кода n=15.

3.12. Требуется передать систематическим кодом, обнаруживающим трехкратные ошибки, все комбинации пятизначного двоичного кода. Чему равна общая длина такого кода n?

3.13. Построить систематический код с кодовым расстоянием d=4, способный передавать 64 сообщения. Какое количество символов n содержит полная комбинация такого кода?

3.14. Определить количество информационных разрядов в систематическом коде длиной n=15 символов, если кодовое расстояние между комбинациями кода d=5?

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

3.16. Какое количество символов первичного алфавита Q можно передать двоичным кодом длиной n=35 символов и минимальным кодовым расстоянием d_min=9?

3.17. Чему равна длина кодовых комбинаций равномерного двоичного кода с минимальным кодовым расстоянием d_min=4, если этим кодом необходимо передавать 8 состояний объектов контролируемой системы?

Рекомендации - при решении задач 3.8, …, 3.17 необходимо иметь в виду, что для обнаружения и исправления одиночной ошибки соотношение между числом информационных разрядов k и числом корректирующих разрядов (n-k) должно определяться условием (2.7), откуда следует неравенство

(2.17)

Для практических расчетов при определении числа контрольных разрядов (n-k) для кодов, исправляющих одиночные либо обнаруживающих двойные ошибки (d_min=3) удобно пользоваться следующим выражением[*]:

(n-k)₁₍₂₎=[log₂(n+1)]. (2.18)

Аналогично для кодов, обнаруживающих все трехкратные ошибки (d_min=4)

откуда

(n-k)₁₍₃₎³1+log₂(n+1). (2.19)

Для кодов длиной n символов, исправляющих одну или две ошибки (d_min=5), с учетом (2.8)

(n-k)₂ log₂( +1), (2.20)

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

(n-k)₂= (2.21)

Для кодов, исправляющих три ошибки (d_min=7), с учетом (2.9)

(n-k)₃= (2.22)

Для кодов, исправляющих S ошибок (d_min=2k+1), с учетом (2.9) можно пользоваться следующей приближенной формулой:

(n-k)_s= (2.23)

3.18. Определить корректирующие способности следующего кода:

а)1101001010 b)101010101 c)1110100100 d)10011010110

0110010111 011001011 1101010111 11000101010

1011100001 110111100 0001110101 01110011101

e)000110010 f)1001101000 g)001000011 h)00111010101

111011001 0100011110 010101010 10001100010

010111101 1001101000 100110100 01100101001

3.19. Заданы подмножества М₁, М₂, М₃ двоичных кодовых слов. Какие из этих подмножеств являются группами, а какие - не являются? Объясните причины.

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

a) 0011; b) 0101; c) 0100; d) 0111;

e) 1001; f) 1011; g) 1101; h) 1100.

Показать процесс исправления ошибок в третьем и шестом разрядах

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

a) 1100001; b) 1101001; c) 1100110; d) 1100010;

0100100. 1010101. 0011010. 1001100.

e) 0110100; f) 1110101; g) 0101010; h) 0001100.

0101011. 0101101. 0101111. 0011110.

3.22. Построить систематический код (6.3), исправляющий одиночные ошибки.

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

a) 01;

b) 11.

3.24. Для одноразрядной кодовой комбинации построить пятиразрядный код (5, 1), исправляющий все одиночные и двойные ошибки. Нумерация разрядов - справа налево.

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

a) 01110011 b) 01111100 c) 00011111 d) 10001111

10011111 11100011 01101100 11101100

11111100 00001101 11110011 11100011

e) 00011111 f) 01100001 g) 11101100 h) 00011111

11001100 00001111 11100011 11110011

01100011 11111100 10011110 01011100

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

a) 0011; b) 0101; c) 0100; d) 0001;

e) 1101; f) 1100; g) 1000; h) 1111.

Показать процесс исправления ошибки в третьем разряде.

Показать процесс обнаружения двойной ошибки.

3.27. Получены четыре комбинации кода (8,4), обнаруживающего двойные ошибки или исправляющего одиночные ошибки. Проверить, верно ли передана каждая из комбинаций, и при необходимости, исправить ошибку. Нумерация разрядов кодового слова справа налево.

a) 01101111 b) 01100001 c) 00111110 d) 01001011

00110100 11000111 00110011 11010001

01100010 10101010 10010110 00101010

10011001 11011000 11100110 11101111

e) 11010010 f) 11100111 g) 10011110 h) 11011001

00001101 11100001 001011001 10110011

11111000 10110000 01111000 11001111

11011011 10101101 11011100 01010101

4. Контрольные вопросы

4.1. Сформулируйте и поясните основную теорему Шеннона о кодировании для канала с помехами.

4.2. Какие коды называются корректирующими?

4.3. Что подразумевают под кратностью ошибки?

4.4. Как определяется расстояние между кодовыми комбинациями?

4.5. Как определяется минимальное кодовое расстояние?

4.6. Как связаны корректирующие способности кода с кодовым расстоянием?

4.7. Каким образом вводится избыточность при построении помехоустойчивого кода?

4.8. В чем сущность помехоустойчивого кодирования?

4.9. Что понимается под значностью и весом кодовой комбинации?

4.10. Что понимается под разделимыми блочными кодами?

4.11. Что понимается под систематическими и несистематическими блочными кодами?

4.12. Какой помехоустойчивый код называется линейным?

4.13. Как происходит исправление ошибки помехоустойчивого кода?

4.14. Представьте основные положения алгебры групп.

4.15. Что такое вектор ошибки?

4.16. Что такое вес вектора ошибки?

4.17. Какими показателями можно оценить качество корректирующих кодов?

4.18. Как строится код, исправляющий все одиночные ошибки?

4.19. Что составляет суть методики построения корректирующих кодов Хэмминга?

4.20. Проиллюстрируйте процесс исправления ошибки в коде (7, 4).

4.21. Постройте кодирующее и декодирующее устройства кода Хэмминга (7, 4).

4.22. Как строится код, исправляющий все одиночные и двойные ошибки (8, 2)?

4.23. Как строится код (8, 4), обнаруживающий двойные ошибки или исправляющий одиночные ошибки?

Библиографический список

1. Дмитриев В.И. Прикладная теория информации/В.И.Дмитриев. - М.: Высшая школа, 1989. - 320с.
2. Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования/Кузьмин И.В., Кедрус В.А. - Киев: Вища школа, 1977. - 280с.
3. Фано Р. Передача информации. Статистическая теория связи/Р. Фано - М.: Мир, 1965. - 438с.
4. Хэмминг Р.В. Теория кодирования и теория информации/Р.В. Хэмминг - М.: Радио и связь, 1983. - 176с.
5. Цымбал В.П. Задачник по теории информации и кодированию/В.П. Цымбал. - К.: Вища шк., 1976. - 276с.
6. Цымбал В.П.Теория информации и кодирование/В.П.Цымбал. - К.: Вища шк., 1992. - 261с.
7. Шеннон К. Работы по теории информации и кибернетике/К.Шеннон - М: Иностранная литература, 1963.
8. Методические указания к практическим занятиям, часть 1, по дисциплине «Теория информации и кодирование» на тему «Вычисление информационных характеристик систем связи»для студентов специальности 7.091501 «Компьютерные системы и сети» дневной и заочной форм обучения./Сост. Щепин Ю.Н. - Севастополь, Изд-во СевНТУ, 2003. - 24с.
9. Методические указания к практическим занятиям по дисциплине «Теория информации и кодирование». Часть 2 «Эффективные коды» для студентов направления подготовки 0915 - "Компьютерная инженерия" дневной и заочной форм обучения/Сост. Щепин Ю.Н. – Севастополь, Изд-во Сев НТУ, 2010. – 28 с.

Заказ № ___ от «___» _________ 2010 г. Тираж ___ экз.

Изд-во СевНТУ

[*] В выражениях (2.18), (2.21), (2.22), (2.23) квадратные скобки означают, что берется значение, округленное до ближайшего целого сверху. Индекс при (n-k) показывает количество ошибок, исправляемых данным кодом, а число в круглых скобках при индексе - число обнаруживаемых ошибок.

Поиск по сайту: