Файл: Методы кодирования данных (Основные понятия теории кодирования).pdf

Введем следующие обозначения:

• t_i – число (кратность) исправляемых ошибок;
• d₀ – расстояние между разрешенными комбинациями.

Следовательно, получим условие, при котором код сможет исправить ошибки (2):

d₀ ≥ 2t_i + 1 (2)

Для построения помехоустойчивого кода необходимо к k информационным разрядам добавить r проверочных. Число проверочных разрядов, которое требуется для построения кода, способного исправить одну ошибку вычисляется по формуле (3):

2^r ≥ k + r + 1 (3)

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

Экономичность и эффективность кодов с обнаружением ошибок определяют особые параметры: коэффициент избыточности (4) и коэффициент обнаружения (5).

R_U = 1 – ln(M₁) / ln(M) (4)

K₀ = Q / (Q + Q₁) (5)

где М = 2ⁿ – общее количество кодовых слов, которое может быть получено в n‑элементном коде;

М₁ – число используемых комбинаций;

Q – общее число искаженных комбинаций, в которых может быть обнаружена ошибка;

Q₁ – общее количество искаженных комбинаций, в которых не может быть обнаружена ошибка [1].

4.1. Коды Хэмминга

Рассмотрим правила построения [7, 4] кода Хэмминга, исправляющего одну ошибку в передаваемой информационной комбинации (a₁, a₂, a₃, a₄). Выпишем таблицу истинности для трех проверочных разрядов:

Где а_i – информационные разряды, а b_i – проверочные.

Тогда, проверочные разряды восстанавливаются по информационным по правилам (6-8):

b₀ = a₁  a₂  a₄ (6)

b₁ = a₁  a₃  a₄ (7)

b₂ = a₂  a₃  a₄ (8)

Таким образом, видно, что значение b₀ формируется из всех a_k, для которых х₀ = 1. Значение b₁ формируется из всех а_k, для которых х₁ = 1 и т.д.

На передатчик канала связи подается самокорректирующийся код Хэмминга [7, 4], имеющий вид (b₀, b₁, a₁, b₂, a_2, a₃, a₄). На приемном конце считаются проверочные символы (9-11):

В₀ = a₁  a₂  a₄ (9)

В₁ = a₁  a₃  a₄ (10)

В₂ = a₂  a₃  a₄ (11)

Разница между принимаемыми В_i и передаваемыми b_i проверочными разрядами позволяет обнаружить и локализовать ошибку.

4.2. Циклические коды

Циклические коды представляют собой обобщение кодов Хэмминга. В данном коде произвольная кодовая последовательность a = (a_1, a₂, …, a_n) принимает вид полинома (12):

u(x) = a₁x^n-1 + a₂x^n-2 + … + a_т-2x² + a_n-1x + a_n (12)

Так, например, кодовой последовательности 1011 соответствует многочлен u(x) = 1х³ + 0х² + 1х¹ + 1х⁰ = х³ + х + 1.

При этом вводятся понятия приводимых и неприводимых многочленов. Неприводимый многочлен – это такой, который не может быть представлен в виде произведения многочленов меньшей степени. Приводимый многочлен, напротив, может быть факторизован.

4.3. Сверточные коды

Прежде чем описывать сверточные коды, введем понятие автомата. Автоматом называется система, которая изменяет свое состояние под действием обрабатываемого входного сигнала. В этом случае значения выходного сигнала зависят не только от входного значение, но и от текущего состояния самой системы.

Для описания работы автомата требуется задать:

• вектор значений входного сигнала a = (a₁a₂…a_n);
• вектор внутренних состояний автомата s = (s₁s₂…s_n).

Во время работы на вход автомата подается очередное значение сигнала a_i. В зависимости от текущего состояния s_k автомат изменяет значение сигнала на z_i, но и сам под воздействием входного сигнала меняет свое состояние на s_m. Следующее значение сигнала a_i+1 автомат принимает находясь в состоянии s_m и в соответствии со своим состоянием формирует выходное значение z_i+1, а сам при этом меняет свое состояние на s_n и т.д.

Следовательно, описание работы автомата дополнительно требует следующих параметров:

• вектор возможных значений выходного сигнала z = (z₁z₂…z_n);
• функцию перехода g: (a_ks_k) → (z_k­), создающую значения выходного сигнала z_k из входного s_k с учетом текущего состояния автомата s_k;
• функцию перехода f: (a_ks_k) → (s_k+1­), меняющую состояние автомата s_k на s_m в зависимости от значения принятого сигнала a_k и текущего состояния автомата s_k.

Автомат, обрабатывающий двоичную последовательность и имеющий четыре возможных состояния s = (s₀, s₁, s₂, s₃) называется сверточным кодом. Его принято задавать в виде таблицы (см. таблицу 4).

Таблица 4 – Автомат сверточного кода

ЗАКЛЮЧЕНИЕ

В рамках выполнения данной работы была раскрыта тема основных методов кодирования информации. Важно отличать процессы кодирования и шифрования. Код используется для передачи информации в более удобном виде. А шифр – для засекречивания.

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

Шифрование - Может оставлять прежней форму, но изменяет, маскирует содержание. Для прочтения недостаточно знать только алгоритм шифрования, нужно знать ключ [Лаш].

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

Существует множество способов классификаций методов кодирования. В данной работе рассмотрены основные из них, а именно:

• по условию построения кодовых комбинаций (равномерные и неравномерные);
• по числу уникальных символов (единичные, двоичные и позиционные);
• по форме представления в канале передачи данных (последовательные и параллельные);
• по возможности обнаружения и исправления ошибок (простые и корректирующие);
• по числу одновременно кодируемых символов (алфавитные и блочные).

Рассмотрение методов кодирования проводилось по группам:

• префиксные коды – коды переменной длины, удовлетворяющие условию Фано;
• арифметические коды – коды упаковывания слов первичного алфавита на основании частоты использования символов;
• цифровые коды – различные методы представления чисел.

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

• множество разрешенных комбинаций;
• множество запрещенных комбинаций.

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

Примерами кодов помехоустойчивого кодирования являются коды Хэмминга, циклические коды, а также сверточные коды.

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Гуменюк А.С. Теория информации и кодирования. – Омск: Изд-во ОмГТУ, 2015. -124 с.
2. Думачев В.Н. Теория информации и кодирования – Воронеж: Воронежский институт МВД Росси, 2012. – 248 с.
3. Лашина И.А. Использование заданий по кодированию информации во внеклассной работе по математике в начальной школе, – 2015. – 6 с.
4. Поляков К.Ю., Еремин Е.А. Информатика - М. : БИНОМ. Лаборатория знаний, 2016. - 80 с.
5. Понятов А.А.Теория информации и кодирования - М.: МИИТ, 2016. — 188 с.
6. Чепкунова Е.Г. Пособие к подготовке к экзамену по дисциплине «Теоретические основы информатики». Раздел «Кодирование информации»: Учеб. пособие – Казань: Казанский университет, 2012. – 92 с.
7. Шикина В.Е. Кодирование информации: методические указания – Ульяновск: УлГТУ, 2006. – 56 с.

Электронные ресурсы:

1. Блочное двоичное кодирование. URL: http://studopedia.ru/3_83187_blochnoe-dvoichnoe-kodirovanie.html
2. Большая энциклопедия нефти и газа. Равномерный код. URL: http://www.ngpedia.ru/id88203p1.html
3. Методы арифметического кодирования информации и сравнение их коэффициентов сжатия. URL: http://bibliofond.ru/view.aspx?id=550668
4. Новый принцип кодирования информации для получения субъективной реальности в искусственных нейронных сетях. URL: https://habr.com/post/399881
5. Постановка задачи кодирования, Первая теорема Шеннона. URL: http://studopedia.ru/view_informatika.php?id=27