AA3-2(ECC) (PDF-лекции от Гурова)

ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиЧасть IIКоды, исправляющие ошибки1 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаРазделы I12Блоковое кодирование. Коды ХэммингаГрупповые (линейные) кодыОпределение и свойстваКодирование линейными кодами3Декодирование линейных кодовЦиклические кодыОпределение и основные свойства4Кодирование циклическими кодами и декодированиеКоды БЧХОпределение и основные свойстваКодирование БЧХ-кодами56Декодирование кодов БЧХЗадачи с решениямиЧто надо знать2 / 132ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга3 / 132Задача помехоустойчивого кодирования: подходы к решениюПо каналу с шумом проходит поток битовой информации.Модель потока: случайный некоррелированный.Модель шума: некоторые биты случайно и независимомогут оказаться инвертированными (двоичныйсимметричный канал, нет добавлений/стираний битов).Задача: обеспечить автоматическое исправление ошибок.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование.

Коды Хэмминга3 / 132Задача помехоустойчивого кодирования: подходы к решениюПо каналу с шумом проходит поток битовой информации.Модель потока: случайный некоррелированный.Модель шума: некоторые биты случайно и независимомогут оказаться инвертированными (двоичныйсимметричный канал, нет добавлений/стираний битов).Задача: обеспечить автоматическое исправление ошибок.Подход к решению (один из возможных!):1входящий поток информации разбить на сообщения —непересекающиеся блоки фиксированной длины k;2каждый блок кодировать —а) либо независимо от других — блоковое кодирование;б) либо в зависимости от предыдущих — свёрточноекодирование (турбо-коды и др.).ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга4 / 132Задачи блокового кодированияДалее рассматривается исключительно блоковое кодирование.Есть набор сообщений S1 , . . . , St , длины k каждое, которыенужно передать по каналу связи с шумом.Для обеспечения помехозащишённости вместо этих сообщенийпередают блоки длины n > k каждое — кодовые слова.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга4 / 132Задачи блокового кодированияДалее рассматривается исключительно блоковое кодирование.Есть набор сообщений S1 , .

. . , St , длины k каждое, которыенужно передать по каналу связи с шумом.Для обеспечения помехозащишённости вместо этих сообщенийпередают блоки длины n > k каждое — кодовые слова.Задача (основная): построить код минимальной длины n,позволяющий восстановить сообщение, содержащее не болееr ошибок.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование.

Коды Хэмминга4 / 132Задачи блокового кодированияДалее рассматривается исключительно блоковое кодирование.Есть набор сообщений S1 , . . . , St , длины k каждое, которыенужно передать по каналу связи с шумом.Для обеспечения помехозащишённости вместо этих сообщенийпередают блоки длины n > k каждое — кодовые слова.Задача (основная): построить код минимальной длины n,позволяющий восстановить сообщение, содержащее не болееr ошибок.Задача (вспомогательная): заданыn — длина кода (обычно зависит от параметра(ов) —m, q, .

. .);r — максимальное количество исправимых ошибок.Требуется построить код, максимизирующий число t сообщений,которое можно передать.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаНекоторые понятия, связанные с булевым кубомРешаем вспомогательную задачу — она проще.Напоминание из дискретной математики Норма γe = число единичных координат в γe ∈ Bn.Метрика (вспоминаем, что это такое) на множествебинарных наборов — хэммингово расстояние (⊕ — суммапо mod 2):e = ρ(eα, β)e ⊕ βe .αШар Хэмминга с центром в αe и радиусом r —nodefe 6r .Sr (eα) = βe ∈ B n | ρ(eα, β)5 / 132ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга6 / 132Р.У. ХэммингРичард Уэсли Хэмминг(Richard Wesley Hamming, 1915–1998)— американский математик, работыкоторого в сфере теории информацииоказали существенное влияние накомпьютерные науки и телекоммуникации.В 1950 г. опубликовал способ построениякода, исправляющего одну ошибкуи названный впоследствии его именем.В его честь Институт инженеров по электротехнике иэлектронике (IEEE, Institute of Electrical and ElectronicsEngineers) учредил медаль, которой награждаются ученые,внесшие значительный вклад в теорию информации —медаль Ричарда Хэмминга.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование.

Коды ХэммингаКодовое расстояниеОпределениеМинимальное расстояние между словами кода называетсякодовым расстоянием, символически d.УтверждениеМножество C образует код с исправлением не менее r ошибок,e = ∅ для всех αeесли Sr (eα) ∩ Sr (β)e, βe ∈ C таких, что αe 6= β.7 / 132ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаКодовое расстояниеОпределениеМинимальное расстояние между словами кода называетсякодовым расстоянием, символически d.УтверждениеМножество C образует код с исправлением не менее r ошибок,e = ∅ для всех αeесли Sr (eα) ∩ Sr (β)e, βe ∈ C таких, что αe 6= β.ДоказательствоЕсли при передаче сообщения αe сделано не более r ошибок,то набор останется в шаре Sr (eα).Если шары не пересекаются, то искомое кодовое слово α —ближайшее к полученному набору.7 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга8 / 132Кодовое расстояние...СледствиеУ кода, исправляющего r ошибок, кодовое расстояние должнобыть не менее 2r + 1.Определение кодового расстояния d произвольного кода —сложная задача.Поэтому при помехоустойчивом кодировании на первый планвыходит проблема построения кодов с заданным кодовымрасстоянием.Она решается при использовании, например, т.н.

БЧХ-кодов,которые будут рассмотрены далее.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга9 / 132Блоковое кодирование и декодирование: определения итривиальный примерБлоковоекодирование—преобразование сообщений длиныдлины n > k.kвзаимно-однозначноев кодовые словаДекодирование — обратное преобразование.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование.

Коды Хэмминга9 / 132Блоковое кодирование и декодирование: определения итривиальный примерБлоковоекодирование—преобразование сообщений длиныдлины n > k.kвзаимно-однозначноев кодовые словаДекодирование — обратное преобразование.Пример (тривиальный код k = 1, n = 3, d = 3)Информация разбивается на блоки длины k = 1, т.е.передаются два сообщения: S0 = 0 и S1 = 1.Кодирование0 7→ 0001 7→ 111исправляет одну ошибку!Однако такое кодирование (выбор k = 1 ) крайненеэффективно: длина сообщения утраивается.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаБлоковое кодирование: обозначения и определенияОбозначим одно сообщение длины k вектором-столбцом(полужирный шрифт) u ∈ {0, 1}k :u1u =  ··· ,ukсодержащим информационные биты u1 , . . . , uk .Определениеv — кодовое слово длины n = k + m, содержащее помимоk информационных, m проверочных бит;Множество {v 1 , . .

. , v 2k } всех 2k кодовых слов длиныn — (n, k)-код (иногда указывают кодовое расстояние ипишут (n, k, d)-код);R = k/n — скорость, m/n = 1 − R — избыточность кода.10 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаБлоковый (n, k) код: кодирование и ошибки передачиБлоковое кодирование не вызывает принципиальныхтрудностей: отображение S → C всегда может бытьосуществлено с использованием таблицы размера 2k ×n(что, однако, весьма неэффективно).11 / 132ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаБлоковый (n, k) код: кодирование и ошибки передачиБлоковое кодирование не вызывает принципиальныхтрудностей: отображение S → C всегда может бытьосуществлено с использованием таблицы размера 2k ×n(что, однако, весьма неэффективно).При передаче по каналу с шумом кодовое слово vпревращается в принятое слово w той же длины n:v → w = v + e.Здесь e ∈ {0, 1}n — вектор ошибок:1, если в i-ом бите произошла ошибка.ei =0, если ошибки нет.(n, k, d)-код исправить не менее [ (d − 1)/2 ] ошибок.11 / 132ПРИКЛАДНАЯ АЛГЕБРА.

Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды Хэмминга12 / 132Блоковый (n, k) код: декодированиеДекодирование любых кодов всегда значительно сложнеекодирования.Декодирование (n, k, d)-кода основано на:разбиении единичного куба B n на k областей,содержащих шары радиуса r = [ (d − 1)/2 ] с центрами вкодовых словах;предположении, что при передаче произошло минимальноеколичество ошибок.ПРИКЛАДНАЯ АЛГЕБРА. Часть II: Коды, исправляющие ошибкиБлоковое кодирование. Коды ХэммингаБлоковый (n, k) код: два этапа декодированияb—1-й этап: Восстановление переданного кодового слова vкак ближайшего к w в метрике Хэмминга, т.е.нахождение центра соответствующего шара.Для этого надо, вообще говоря, перебрать все 2kстрок в 2k ×n-таблице кодовых слов.Если расстояние до ближайшего центра шара(кодового слова) превышает величинуr = [ (d − 1)/2 ], то при передаче произошлобольше ошибок, чем может исправить код иалгоритм декодирования должен выдать отказ.b исходного сообщения ub—2-й этап: Восстановление по vпутём удаления проверочных бит.В общем случае это потребует использованиятаблицы размера 2k ×k.13 / 132ПРИКЛАДНАЯ АЛГЕБРА.