Кодирование Петухов Дмитрий Кодирование
 Скачать 0.5 Mb.
|
 Кодирование Петухов Дмитрий Кодирование Кодирование представляет собой преобразование сообщения в последовательность некоторых символов. Для этого устанавливают взаимооднозначное соответствие между сообщениями и символами, которое называется кодом.  Кодирование При кодировании происходит процесс преобразования элементов сообщения в соответствующие им числа (кодовые символы). Каждому элементу сообщения присваивается определенная совокупность кодовых символов, которая называется кодовой комбинацией. Совокупность кодовых комбинаций, обозначающих дискретные сообщения, образует код.  Декодирование Декодирование – это процесс восстановления сообщения по принимаемым кодовым символам. Устройства, осуществляющие кодирование и декодирование, называются соответственно кодером и декодером.  Декодирование   Этот метод требует упорядочения исходного множества символов по не возрастанию их частот. Затем выполняются следующие шаги: а) список делится на 2 части так, чтобы суммы частот обеих частей были примерно или точно равны; б) кодовым комбинациям первой части дописывается 1, второй части – 0; в)анализируют первую часть: если она содержит только один символ, работа с ней заканчивается, и переходят к шагу г). Иначе переходят к шагу а) и обрабатывают первую часть как самостоятельный список; г) анализируют вторую часть аналогично первой.   Исходное множество символов упорядочивается по не возрастанию частоты и выполняются следующие шаги: 1) Объединение частот: две последние частоты складываются, соответствующие символы исключаются из списка и заменяются полученной суммой. Список вновь упорядочивается. Это повторяется до тех пор, пока не получится единица в результате суммирования и список не уменьшится до одного символа. 2) Построение кодового дерева.   Кодовое расстояние Кодовым расстоянием называется число различных разрядов в кодовых комбинациях i и j. Кодовым расстоянием d для кода, содержащего m комбинаций, является минимальное расстояние между всеми парами кодовых комбинаций. , где  Пусть есть кодовая таблица: Пусть есть кодовая таблица: Тогда Это означает, что ошибка кратности 1 и более переводит исходную кодовую комбинацию в другую, которая также принадлежит коду.  Помехоустойчивое кодирование Построение помехоустойчивого кода достигается путем введения избыточности. Избыточность кода – это количество проверочной информации в сообщении. , – количество проверочных бит, – количество информационных бит.  Помехоустойчивое кодирование. Код с проверкой на четность Этот метод служит для определения нечетного количества ошибок  Помехоустойчивое кодирование. Коды Хэмминга Каждый проверочный код представляет собой сумму по модулю 2 некоторой последовательности данных. Проверочные символы располагаются на позициях, равных степеням двойки в порядке возрастания. Первый проверочный бит на 20=1, второй – 21=2, третий 22=4 и т.д.   Закодируем 4 бита информации Закодируем 4 бита информации i1 i2 i3 i4 0 1 0 1 В закодированном сообщении должно быть: r1 r2 i1 r3 i2 i3 i4 r1 r2 0 r3 1 0 1 Рассчитаем проверочные символы: r1=i1+i2+i4=0 r2=i1+i3+i4=1 r3=i2+i3+i4=0 Получаем последовательность: 0 1 0 0 1 0 1  0 1 0 0 0 0 1 Заново вычисляются все контрольные биты. r1=0+0+1=1 r2=0+0+1=1 r3=0+0+1=1 Получаем: 1 1 0 1 0 0 1 Сложив номера неправильных контрольных бит получаем позицию ошибки. 1+4=5 Инвертируем этот бит и получаем исходное сообщение. 0 1 0 1  |