Идея кодирования. Блоковые коды

Курсовая работа по предмету: «Фундаментальная и компьютерная алгебра» на тему: «Элементы теории кодирования»

Выполнила:

Студентка I курса

Группы 123-1

Подоляк Т.А

Проверил:

К. ф.-м. н. доцент

Иванов Д.И.

Тюмень 2013г.

Оглавление.

№ Наименование № стр.

1. Введение……………………………………………………….. 3

2. Основные понятия теории кодирования………………….. 4

3. Идея кодирования. Блоковые коды………………............... 4

4. Разрежённость кода. Расстояние Хэмминга………………. 5

5. Примеры кодирования………………………………………. 6

5.1. Простое кодирование с повторением…………………. 6

5.2. Простое кодирование с проверкой на четность……… 6

5.3. Прямоугольные коды…………………………………… 7

6. Линейный код и его порождающая матрица……….. ……. 7

7. Проверочная матрица линейного кода……………………. 8

8. Декодирование линейных кодов……………………………. 9

9. Коды Хэмминга……………………………………………….. 10

10. Заключение……………………………………………………. 12

11. Список литературы…………………………………………... 13

Введение.

Данная работа посвящена ознакомлению с основными понятиями и элементами теории кодирования.

Целью данной работы является:

· Разработка методов надежной передачи информации;

· Выбор лучших параметров кодирования;

· Поиск лучших алгоритмов кодирования;

· Поиск лучших алгоритмов декодирования.

- 3 –

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

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

Кодирование - это преобразования информации в формулу удобную для передачи по определенному каналу связи.

Декодирование - восстановление принятого сообщения из-за кодированного вида в вид доступный для потребителя.

Кодер - заменяет информационные слова кодовыми согласно таблице кодирования. Кодовые слова передаются по каналу связи и поступают,

возможно с искажениями, в декодер.

Декодер - Если принято одно из кодовых слов, то декодер произведет

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

Идея кодирования. Блоковые коды.

К каждому из блоков данной длины k, подлежащих передаче, следует приписать еще некоторое число r дополнительных символов, приняв некоторое правило, по которому строятся эти r символов из k первоначальных, и передавать по каналу связи блоки длины n = k + r.

Определение 1. Блоковый код над алфавитом A — это множество последовательностей определенной длины n, составленных из элементов множества A. Число n называется длиной кода, а элементы кода — блоками или словами кода. Вообще, слово над алфавитом A (или слово в алфавите A) — это последовательность элементов из множества A. Множество всех

слов длины n над A обозначается через W(n, A).

Таким образом, блоковый код длины n над алфавитом A — это любое подмножество из W(n, A). Коды над любым алфавитом из q символов называются q-ичными. Если символы алфавита записываются слитно, то запятые между ними в слове не ставятся.

Определение 2. Пусть M — некоторое множество слов длины k в алфавите A. Кодированием множества M называется взаимно однозначное отображение множества M на некоторое множество слов определенной длины n в том же алфавите.

На практике в качестве M берется обычно все множество W(k, A) (так как передавать приходится большие тексты). Поэтому, если |A| = q, то |M| = q^k. Понятно, что кодирование такого множества M имеет смысл использовать лишь при n > k. Это — ”принцип избыточности” информации при кодировании.

- 4 -

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