Понятие о теории кодирования.

Понятие о теории кодирования. Кодирование информации имеет огромное значение в различных вопросах кибернетики и дискретной математики: в теории передачи информации, защиты информации, проектировании цифровых систем и т. д. Рассмотрим подробную схему канала связи: Источник информации преобразователь кодер модулятор шум Получатель информации Преобразователь (обратный) декодер канал связи демодулятор Основная проблема в том, что шум может искажать сигнал, но информацию желательно восстановить, поэтому кодер и декодер должны обладать возможностями обнаружения и исправления ошибок, вызванных шумом. Нужны коды, исправляющие ошибки (коды, контролирующие ошибки). История кодирования, контролирующего ошибки, началась в 1948 году со статьи Клода Шеннона. Он доказал, что у каждого канала связи есть своя пропускная способность, то есть при скорости передачи информации меньше некоторой v (бит/с), используя коды, исправляющие ошибки, можно сделать вероятность ошибки сколь угодно малой. Таким образом, создание слишком хороших и дорогих каналов связи экономически невыгодно – выгодно кодирование информации. Первые нетривиальные коды, исправляющие ошибки, создал Ричард Хемминг в 1950 году. Введем основные понятия. Опр. Абстрактным алфавитом называется множество F из конечного числа фиксированных символов – букв. Слово – любая конечная упорядоченная последовательность букв. Примеры: 1. Русский алфавит (кириллица) – 33 буквы. 2. Цифровой алфавит (арабские цифры) – {0, …, 9} – буквы, 000, 1024, 1153 – слова. 3. Двоичный алфавит – двоичные буквы (и слова). Опр. Инъективное отображение из одного алфавита во множество слов другого алфавита называется кодом. То есть это f: F1 → W(F2), где W(F2) – множество слов алфавита F2 (может быть F1 = F2 ). Примеры: 1. Кодирование кириллицы латиницей (транслитерация, транслит): а → a, б → b, ы → y, ё → jo, ч → tch, щ → sch. 2. Код (азбука) Морзе состоит из точек и тире (короткий и длинный звук) { • , –}. Кодируем кириллицу: а → б→– с • – ••• ••• о––– и т.д. Можно передавать буквы по радиосвязи. Сейчас это уже устарело. 3. Кодирование кириллицы числами: Выбросим букву ё и перекодируем в десятичные или двоичные числа а → 0 → 00000 б → 1 → 00001 ... е → 6 →00110 ж → 7 →00111 ... я → 31 → 11111 4. Простой код с проверкой на четность: к двоичному слову дописывается один бит так, чтобы число единиц стало четным: 001 → 0011 011 → 0110 Такой код дает возможность обнаружить одну ошибку, но не исправить ее. Вывод: особенно удобны для работы двоичные коды, то есть инъективные отображения f: Bink → Binn (всегда n  k, на практике n > k). Такой код называется двоичным (n,k)-кодом. Коды, исправляющие ошибки (КИО). Такие коды, конечно же, существуют. Пример: Простой код с повторениями 0→000, 1→111. Такой код обнаруживает и исправляет единичную ошибку: например, получив 100, получатель понимает, что передавалось 000, а получив 101, получатель понимает, что передавалось 111 (принцип большинства). Недостаток этого кода- малая скорость, он в 3 раза замедляет передачу информации. Определение: Скорость двоичного (n,k)-кода-это отношение длины исходного слова и закодированного слова = k . n В нашем примере = 1 - низкая скорость. Цель наша →1. 3 Первый нетривиальный код Хемминга оказался (7,4)-кодом. Алгоритм кодера (7,4)-кода Хемминга. 𝑖1 𝑖2 𝑖3 𝑖4 → 𝑖1 𝑖2 𝑖3 𝑖4 𝑝1 𝑝2 𝑝3 ; 𝑝1 = 𝑖1 + 𝑖2 + 𝑖3 (𝑚𝑜𝑑 2) 𝑝2 = 𝑖2 + 𝑖3 + 𝑖4 (𝑚𝑜𝑑 2) 𝑝3 = 𝑖1 + 𝑖2 + 𝑖4 (𝑚𝑜𝑑 2) Закодируем этим кодером все 16 слов из Bin4: 0000 → 0000000 0001 → 0001011 0010 → 0010110 ⋯⋯ {1111→1111111 Как проверить, что получился код, исправляющий единичные ошибки? Приведем алгоритм декодера, позволяющий обнаруживать и исправлять единичные ошибки, это автоматически означает, что получен код Хемминга. Алгоритм декодера (7,4)-кода Хемминга. Пусть вместо закодированного слова 𝑖1 𝑖2 𝑖3 𝑖4 𝑝1 𝑝2 𝑝3 получено слово 𝑖̃1 𝑖̃2 𝑖̃3 𝑖̃4 𝑝̃1 𝑝̃2 𝑝̃3 , содержащее не более одной ошибки (неизвестно, в каком бите). Вычислим три двоичных числа: ~ ~ ~ S1 = i1 + i2 + i3 + ~ p1 (mod 2) ~ ~ ~ S =i +i +i +~ p (mod 2) 2 2 3 4 2 ~ ~ ~ S 3 = i1 + i2 + i4 + ~ p3 (mod 2) Составим из них двоичное слово S1 S 2 S3 – так называемый синдром. Синдромов теоретически может быть 23=8. Докажем, что каждый из них однозначно соответствует ошибке в бите с 1-го по 7-ой, либо отсутствию ошибок. Разберем все 8 таких случаев. 0-й случай: Отсутствие ошибок. Тогда 𝑖̃1 = 𝑖1 , … , 𝑝̃3 = 𝑝3 Вычисляем 𝑆1 = 𝑖1 + 𝑖2 + 𝑖3 + 𝑝1 = 𝑝1 + 𝑝1 = 0 𝑆2 = 𝑖2 + 𝑖3 + 𝑖4 + 𝑝2 = 𝑝2 + 𝑝2 = 0 𝑆3 = 𝑖1 + 𝑖2 + 𝑖4 + 𝑝3 = 𝑝3 + 𝑝3 = 0 Получили синдром 000. 1-й случай: Ошибка в 1-ом бите. Тогда ~ i1 = i1 + 1 , а остальные не искажены. Вычисляем 𝑆1 = 𝑖1 + 1 + 𝑖2 + 𝑖3 + 𝑝1 = 𝑝1 + 𝑝1 + 1 = 0 𝑆2 = 𝑖2 + 𝑖3 + 𝑖4 + 𝑝2 = 𝑝2 + 𝑝2 = 0 𝑆3 = 𝑖1 + 1 + 𝑖2 + 𝑖4 + 𝑝3 = 𝑝3 + 𝑝3 + 1 = 1 Получили синдром 101. 2-й случай: Ошибка во 2-ом бите. Тогда 𝑖̃2 = 𝑖2 + 1, а остальные не искажены. Вычисляем 𝑆1 = 𝑖1 + 𝑖2 + 1 + 𝑖3 + 𝑝1 = 𝑝1 + 𝑝1 + 1 = 1 𝑆2 = 𝑖2 + 1 + 𝑖3 + 𝑖4 + 𝑝2 = 𝑝2 + 𝑝2 + 1 = 1 𝑆3 = 𝑖1 + 𝑖2 + 1 + 𝑖4 + 𝑝3 = 𝑝3 + 𝑝3 + 1 = 1 Получили синдром 111. 3-й случай: Ошибка в 3-ем бите. Аналогично вычисляем синдром 110. 4-й случай: Ошибка в 4-ом бите. Синдром 011. 5-й случай: Ошибка в 5-ом бите. Синдром 100. 6-й случай: Ошибка в 6-ом бите. Синдром 010. 7-й случай: Ошибка в 7-ом бите . Синдром 001. Поскольку все синдромы получились различными, то получатель с помощью синдрома однозначно определяет, в каком из 7 битов ошибка (или её нет), автоматически исправляет её с помощью отрицания (инверсии) и отбрасывает три последних добавленных символа: 𝑖̃1 𝑖̃2 𝑖̃3 𝑖̃4 𝑝̃1 𝑝̃2 𝑝̃3 →𝑖1 𝑖2 𝑖3 𝑖4 𝑝1 𝑝2 𝑝3 →𝑖1 𝑖2 𝑖3 𝑖4 . Так работает декодер. РГР «Код Хемминга» Имеется кириллическое слово из 8 букв. Каждая буква кодируется 5-битовым двоичным словом по алфавитному коду: а00000, б00001, в00010, г00011, д00100, е00101, ж00110, з00111, и01000, й01001, к01010, л01011, м01100, н01101, о01110, п01111, р10000, с10001, т10010, у10011, ф10100, х10101, ц10110, ч10111, ш11000, щ11001, ъ11010, ы11011, ь11100, э11101, ю11110, я11111. Букву Ё мы удалили из алфавита, чтобы нам хватило 32х 5-битовых слов. Получили 8х5=40-битовое двоичное слово. Для передачи по каналу связи его разрезают на 10 4-битовых двоичных слов, каждое из которых кодируют с помощью кодера (7,4)-кода Хемминга. Задание: Получив персональное сообщение из десяти 7-битовых слов и проделав все указанные действия в обратном порядке, восстановить исходное кириллическое слово из 8 букв. О существовании кодов Хемминга Теорема. Существует бесконечно много (n,k)- кодов Хемминга для всех n=2m–1, k=2m–m–1, m=2,3,4,… i1 , i2 ,...ik → i1 , i2 ,...ik p1 p 2 ... p k Идея доказательства: k + m = (2 m − m − 1) + m = 2 m − 1 = n , здесь pi – сумма некоторых ik , как и в (7,4)-коде Хемминга. Заполним таблицу таких кодов: m n k 2 3 1 3 7 4 4 15 11 5 31 26 … … … Мы видим здесь и тривиальный (3,1)-код, и наш (7,4)- код Хемминга, и другие новые. Ясно, что из скорости v растут и приближаются к единице. Однако увлекаться очень длинными закодированными словами не следует, так как в них уже становятся более вероятными две и более ошибки, и декодер не сможет их раскодировать. Замечание. Не следует думать, что в теореме описаны ВСЕ возможные КИО. Например, чуть позже мы узнаем, что существует (6,3)-код Хемминга, не описанный в нашей теореме. АНАЛИЗ РАССТОЯНИЙ ХЕММИНГА Опр. Расстояние Хемминга между двумя двоичными словами X и Y одинаковой длины – это число позиций (битов), в которых они отличаются. Обозначаем d(X,Y) или просто d. Пример. X=10101, Y=01001. Тогда d=3. ̃) = 1 означает Заметим, что d(X,Y)=0 означает совпадение слов, а d(X, X единичную ошибку. Теорема (критерий Хемминга) Двоичный код исправляет единичные ошибки  для любых двух закодированных слов X и Y d(X,Y)  3. Доказательство. Рисуем схему. 𝑋→ 𝑌→ 𝑑=1 𝑑=1 𝑋̃ 𝑌̃ Ясно, что для успешного декодирования должно быть 𝑋̃ 𝑌̃ , то есть 𝑑(𝑋̃, 𝑌̃)  1 Пройдя по кругу схемы, получаем, что d(X,Y)  1+1+1= 3, ч.т.д. Замечание. Теперь мы могли бы проверить, что (7,4)-код Хемминга исправляет единичные ошибки еще до построения декодера, по критерию Хемминга. Для 2 этого потребовалось бы С16 = 120 проверок. Критерий позволяет теоретически доказывать НЕсуществование некоторых (n,k)-кодов Хемминга. Предложение. Если существует (n,k)-код Хемминга, то существует и (n,k)-код Хемминга, содержащий нулевое слово 00…0. Идея док-ва. Выбираем любое слово из кода и применяем ко ВСЕМ кодовым словам одно и то же преобразование – инверсию на позициях, где в выбранном слове стоят единицы. Такое преобразование, очевидно, не меняет расстояние Хемминга, поэтому новый код тоже исправляет единичные ошибки. Но в нем уже точно есть нулевое слово. Пример. Доказать, что не существует (4,2)-код Хемминга. Решение. Рассмотрим слово 0000. Тогда остальные кодовые слова, согласно критерию Хемминга, содержат не менее 3х единиц. Если среди них есть слово с 4 единицами, то остальные вообще невозможны, так как тогда d=1. Если же есть только слова с 3 единицами, то между ними d=2, что тоже не устраивает. Упражнение*. Аналогично доказать, что не существует (5,3)-код Хемминга. КОДЫ, ИСПРАВЛЯЮЩИЕ НЕСКОЛЬКО ОШИБОК Теорема (усиленный критерий Хемминга) Двоичный код исправляет r ошибок  для любых двух закодированных слов X и Y d(X,Y)  2r+1. Доказательство. Рисуем схему 𝑋→ 𝑌→ 𝑑=𝑟 𝑑=𝑟 𝑋̃ 𝑌̃ Ясно, что для успешного декодирования должно быть 𝑋̃ 𝑌̃ , то есть 𝑑(𝑋̃, 𝑌̃)  1 Пройдя по кругу схемы, получаем, что d(X,Y)  r+r+1=2r+1, ч.т.д. Например, код исправляет две ошибки, если d(X,Y)  22+1=5. Пример Построим тривиальный (5,1)-код Хемминга: 0→00000, 1→11111. Тогда d(X,Y)=5 и усиленный критерий показывает, что он исправляет две ошибки. Но скорость v=1/5 очень мала. Для получения более быстрых КИО можно использовать Прием клонирования двоичных кодов На основе (7,4)-кода Хемминга создадим (14,8)-код, клонировав его по формулам 𝑖1 𝑖2 𝑖3 𝑖4 𝑗1 𝑗2 𝑗3 𝑗4 → 𝑖1 𝑖2 𝑖3 𝑖4 𝑝1 𝑝2 𝑝3 𝑗1 𝑗2 𝑗3 𝑗4 𝑞1 𝑞2 𝑞3 , где 𝑝1 = 𝑖1 + 𝑖2 + 𝑖3 (𝑚𝑜𝑑 2) 𝑝2 = 𝑖2 + 𝑖3 + 𝑖4 (𝑚𝑜𝑑 2) 𝑝3 = 𝑖1 + 𝑖2 + 𝑖4 (𝑚𝑜𝑑 2) 𝑞1 = 𝑗1 + 𝑗2 + 𝑗3 (𝑚𝑜𝑑 2) 𝑞2 = 𝑗2 + 𝑗3 + 𝑗4 (𝑚𝑜𝑑 2) 𝑞3 = 𝑗1 + 𝑗2 + 𝑗4 (𝑚𝑜𝑑 2) Здесь, очевидно, d(X,Y)  3+3=6, значит, по усиленному критерию код исправляет две ошибки. Отметим, что клонировать декодер (7,4)-кода Хемминга здесь не удается, так как могут быть две ошибки в первой половине полученного слова (или же во второй). Эффективного декодера мы предложить не можем. Неэффективный декодер, конечно, существует: нужно занести в файл компьютера все 28=256 закодированных слов без ошибки и сравнить со всеми ними полученное слово – обязательно найдется ровно одно из 256. Затем надо удалить из слова «лишние» символы pk и qk . Аналогично можем создать (21,12)-код, трижды клонировав (7,4)-код. Здесь уже d(X,Y)  3+3+3=9, и по усиленному критерию мы видим, что код 4 исправляет 4 ошибки. Скорость всех трех кодов одинакова и равна . 7 Для еще более быстрых кодов потребовались более мощные математические методы.