Основные понятия помехоустойчивого кодирования

Лекция 1: Введение Основные понятия помехоустойчивого кодирования 13 февраля 2009 г. Claude Elwood Shannon Shannon C. E. A mathematical theory of communication. — Bell Syst. Tech. J., 1948, v. 27, p. 379–423 (Part I), p. 623–656 (Part II). [Рус. пер.: Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963, с. 243–332.] 30.04.1916 — 26.02.2001 Система связи с помехами шум передатчик кодер канал связи декодер приёмник Система связи с помехами шум передатчик кодер канал связи декодер приёмник искажённая последовательность сообщение декодированная последовательность кодовая последовательность Система связи с помехами шум e x i передатчик кодер канал связи y =x+e декодер приёмник искажённая последовательность сообщение декодированная последовательность кодовая последовательность Пример: F43 3 y = 2011 ⇒ e = y − x = 1020. x = 1021 Двоичный симметричный канал (ДСК) Двоичный симметричный канал с вероятностью ошибки p (без памяти) 1−p p p 1 101101 1−p 1 100101 ДСК(p): Двоичный симметричный канал (ДСК) Двоичный симметричный канал с вероятностью ошибки p (без памяти) 1−p p элементарные ошибки, возникающие в различных разрядах кодовых слов, независимы p 1 101101 1−p ДСК(p): 1 100101 Двоичный симметричный канал (ДСК) Двоичный симметричный канал с вероятностью ошибки p (без памяти) 1−p p элементарные ошибки, возникающие в различных разрядах кодовых слов, независимы p 1 101101 1−p ДСК(p): 1 100101 схема Бернулли Двоичный симметричный канал (ДСК) Двоичный симметричный канал с вероятностью ошибки p (без памяти) 1−p p элементарные ошибки, возникающие в различных разрядах кодовых слов, независимы p 1 101101 1−p ДСК(p): 1 100101 схема Бернулли P(yx) P(y|x) = ∼ P(yx) P(x) передаваемые по каналу сообщения равновероятны Некоторые другие виды каналов связи Несимметричный канал 1 − p1 Канал со стиранием p1 Канал с выбрасыванием − λ p2 1 1 1 1 − p2 p1 6= p2 1 1 1 1011 10−1 1011 101 Зачем нужны кодер и декодер? Пример: Пусть при передаче одного бита по ДСК ошибка происходит с вероятностью p = 10−3 . Тогда вероятность безошибочной передачи n бит равна P0 (n) = (1 − p)n = 0,999n P0 (n) экспоненциально убывает. P0 (103 ) < 0,37 P0 (104 ) < 5 · 10−5 ⇒ уже при сравнительно небольшой длине сообщения необходимо использовать код, корректирующий ошибки. Блочное и поточное кодирование Общая идея: для исправления ошибок при хранении/передаче информации используется некоторая избыточность. Помехоустойчивые коды Блочное кодирование Поточное кодирование (block codes) свёрточные коды (convolutional codes) Инормационная последовательность с символами из Fq делится на блоки длины k и каждый из них независимо кодируется блоком x длины n. Блок x передаётся по каналу с шумом, канал вносит ошибки и получается блок y. В отличие от блочного кода, выход свёрточного кодера зависит от (потенциально всех) предыдущих символов на его входе или выходе. 00 Свёрточный код 10 00 ... 00 10 ... 10 00 ... 10 ... 01 ... 00 11 ... 10 01 ... 11 ... Блочный код с о о б щ е н и е Блочный код k k k z }| { z }| { z }| { с о о б щ е н и е Блочный код k k k z }| { z }| { z }| { с о о б щ е н и е a b c d e f g h i j k l | {z } | {z } | {z } n n n Скорость блочного кода Определение Преобразование Ψ, ставящее в соответствие каждому информационному слову i длины k слово x длины n, называется кодированием. x = Ψ(i) — кодовое слово C = {x = Ψ(i) : ∀i} — блочный код длины n Кодовая таблица кода C — таблица, в которой выписаны все кодовые слова. Отношение длин информационного и кодового векторов называется скоростью блочного кода: R= k . n Общая схема использования блочного кода вектор ошибки e ∈ Fnq информационный вектор i ∈ Fkq длины k кодовый вектор x∈ Fnq длины n n>k канал y =x+e i? принятый вектор y ∈ Fnq Систематический блочный код n k z }| { z информация | }| { информация избыточность {z } {z } | k n−k Кодирование, при котором первые (или последние) разряды кодового слова x совпадают с разрядами информационного i, называется систематическим. Эти k разрядов кодового слова называются информационными. Остальные (n − k) разрядов называются проверочными. Проверочные разряды служат для восстановления информационных при декодировании. Пример: пусть p < 12 ... y = 10101  00 → 00001    01 → 01010 Ψ: 10 → 10111    11 → 11100 Пример: пусть p < 12 ... y = 10101 x  00 → 00001    01 → 01010 Ψ: 10 → 10111    11 → 11100 00001 01010 10111 11100 P(y|x) Пример: пусть p < 12 ... y = 10101  00 → 00001    01 → 01010 Ψ: 10 → 10111    11 → 11100 x P(y|x) 00001 01010 10111 11100 p 2 (1 − p)3 Пример: пусть p < 12 ... y = 10101  00 → 00001    01 → 01010 Ψ: 10 → 10111    11 → 11100 x P(y|x) 00001 01010 10111 11100 p 2 (1 − p)3 p5 Пример: пусть p < 12 ... y = 10101  00 → 00001    01 → 01010 Ψ: 10 → 10111    11 → 11100 x P(y|x) 00001 01010 10111 11100 p 2 (1 − p)3 p5 p(1 − p)4 Пример: пусть p < 12 ... y = 10101  00 → 00001    01 → 01010 Ψ: 10 → 10111    11 → 11100 x P(y|x) 00001 01010 10111 11100 p 2 (1 − p)3 p5 p(1 − p)4 p 2 (1 − p)3 Пример: пусть p < 12 ... y = 10101  00 → 00001    01 → 01010 Ψ: 10 → 10111    11 → 11100 x P(y|x) 00001 01010 10111 11100 p 2 (1 − p)3 p5 p(1 − p)4 p 2 (1 − p)3 p 5 < p 2 (1 − p)3 < p(1 − p)4 Пример: пусть p < 12 ... y = 10101  00 → 00001    01 → 01010 Ψ: 10 → 10111    11 → 11100 x P(y|x) 00001 01010 10111 11100 p 2 (1 − p)3 p5 p(1 − p)4 p 2 (1 − p)3 p 5 < p 2 (1 − p)3 < p(1 − p)4 ⇒ x = 10111, i = 10 Декодирование: метод максимального правдоподобия ... Декодирование: метод максимального правдоподобия n n n n z }| { z }| { z }| { z }| { ... Декодирование: метод максимального правдоподобия n n n n z }| { z }| { z }| { z }| { y ... «Ψ−1 (y) =?» Декодирование: метод максимального правдоподобия n n n n z }| { z }| { z }| { z }| { y ... «Ψ−1 (y) =?» Декодирование 1 Сначала надо найти x ∈ C, т.ч. P(y|x) = max. 2 i = Ψ−1 (x) Декодирование: метод максимального правдоподобия n n n n z }| { z }| { z }| { z }| { y ... «Ψ−1 (y) =?» Декодирование 1 Сначала надо найти x ∈ C, т.ч. P(y|x) = max. 2 i = Ψ−1 (x) Утверждение Пусть C = {xi }, p < 1/2 и P(y|x) = max P(y|xi ). i Тогда d(y, x) = min d(y|xi ), где d(y, x) — число разрядов, в i которых различаются x и y. Возможные случаи 1 Если max P(y|xi ) достигается на единственном кодовом i слове x, то ошибка исправима: e = y − x. 2 3 4 Вычисление x по y — декодирование (исправление ошибок в y). Пусть передавался x0 ∈ C. Если x = x0 , то декодирование называется правильным, если x 6= x0 — неправильным. Если max P(y|xi ) достигается на нескольких x, то говорят i об обнаружении ошибки (исправить которую нельзя). Расстояние между векторами Fq — поле из q элементов Fnq — множество всех векторов длины n над Fq (Л.В.П.) Определение Пусть α̃, β̃ ∈ Fnq , α̃ = (α1 , . . . , αn ), β̃ = (β1 , . . . , βn ). Расстоянием Хемминга d(α̃, β̃) между наборами α̃, β̃ называется число разрядов, в которых различаются α̃ и β̃. При простом q расстоянием Ли ρ(α̃, β̃) между наборами α̃, β̃ называется величина ρ(α̃, β̃) = n X |αi − βi |. i=1 Упражнение Доказать, что (Fnq , d) и (Fnq , ρ) — метрические пространства. Метрические пространства: определения Пусть X — некоторое множество и ρ : X × X 7→ R — действительнозначная функция. Определение Пара (X , ρ) называется метрическим пространством, а функция ρ — метрикой на X , если для всех a, b, c ∈ X выполняются свойства: Метрические пространства: определения Пусть X — некоторое множество и ρ : X × X 7→ R — действительнозначная функция. Определение Пара (X , ρ) называется метрическим пространством, а функция ρ — метрикой на X , если для всех a, b, c ∈ X выполняются свойства: 1 Симметричность: ρ(a, b) = ρ(b, a); Метрические пространства: определения Пусть X — некоторое множество и ρ : X × X 7→ R — действительнозначная функция. Определение Пара (X , ρ) называется метрическим пространством, а функция ρ — метрикой на X , если для всех a, b, c ∈ X выполняются свойства: 1 Симметричность: ρ(a, b) = ρ(b, a); 2 Неотрицательность: ρ(a, b) > 0 и ρ(a, b) = 0 ⇔ a = b; Метрические пространства: определения Пусть X — некоторое множество и ρ : X × X 7→ R — действительнозначная функция. Определение Пара (X , ρ) называется метрическим пространством, а функция ρ — метрикой на X , если для всех a, b, c ∈ X выполняются свойства: 1 Симметричность: ρ(a, b) = ρ(b, a); 2 Неотрицательность: ρ(a, b) > 0 и ρ(a, b) = 0 ⇔ a = b; 3 Неравенство треугольника: ρ(a, b) + ρ(b, c) > ρ(a, c). Метрические пространства: определения Пусть X — некоторое множество и ρ : X × X 7→ R — действительнозначная функция. Определение Пара (X , ρ) называется метрическим пространством, а функция ρ — метрикой на X , если для всех a, b, c ∈ X выполняются свойства: 1 Симметричность: ρ(a, b) = ρ(b, a); 2 Неотрицательность: ρ(a, b) > 0 и ρ(a, b) = 0 ⇔ a = b; 3 Неравенство треугольника: ρ(a, b) + ρ(b, c) > ρ(a, c). Определение В метрическом пространстве (X , ρ) определены множества: Br (a) = {b ∈ X : ρ(a, b) 6 r } — шар радиуса r с центром a. Sr (a) = {b ∈ X : ρ(a, b) = r } — сфера радиуса r с центром a. Метрические пространства: примеры 1 2 3 4 5 Плоскость R2 = {x = (x1 , x2 ) : xi ∈ R} с евклидовым p расстоянием ρ(a, b) = (a1 − b1 )2 + (a2 − b2 )2 . Плоскость R2 с метрикой манхэттэнского типа d(a, b) = |a1 − b1 | + |a2 − b2 |. Плоскость R2 с метрикой ρ(a, b) = max(|a1 − b1 |, |a2 − b2 |). Произвольное множество U с метрикой  0, a = b ρ(a, b) = . 1, a 6= b Множество 2U = {X : X ⊆ U} всевозможных подмножеств конечного множества U с метрикой ρ(X , Y ) = |X 4 Y |. Вес и номер набора Определение Наборы, различающиеся в единственном разряде, называются соседними, а во всех разрядах — противоположными. Пусть α̃ = (α1 , . . . , αn ) — произвольный набор из Fnq . Тогда величина kα̃k, равная числу ненулевых координат в наборе α̃, называется его весом. P Величина |α̃| = ni=1 αi q n−i называется номером набора α̃. Пример q = 2: k1001k = 2, |1001| = 9. q = 3: k102k = 2, |102| = 1 · 32 + 0 · 31 + 2 · 30 = 11. Наборы 100, 101 ∈ F32 — соседние, а наборы 100, 011 — противоположные. Простейшие факты В случае q = 2 расстояния по Хеммингу и по Ли совпадают: d = ρ, но вообще говоря это не так. Например, при q = 3: d(101, 221) = 2, ρ(101, 221) = |1 − 2| + |0 − 2| + |1 − 1| = 3. Легко видеть, что d(α̃, β̃) 6 ρ(α̃, β̃) для всех α̃, β̃. Дальше под расстоянием между наборами, если не указано иное, будем понимать расстояние Хемминга. r G α̃ = (α1 , . . . , αn ) ∈ Fnq ⇒ Br (α̃) = Sr (α̃) i=0 Простейшие факты В случае q = 2 расстояния по Хеммингу и по Ли совпадают: d = ρ, но вообще говоря это не так. Например, при q = 3: d(101, 221) = 2, ρ(101, 221) = |1 − 2| + |0 − 2| + |1 − 1| = 3. Легко видеть, что d(α̃, β̃) 6 ρ(α̃, β̃) для всех α̃, β̃. Дальше под расстоянием между наборами, если не указано иное, будем понимать расстояние Хемминга. r G α̃ = (α1 , . . . , αn ) ∈ Fnq ⇒ Br (α̃) = Sr (α̃) i=0 |Sr (α̃)| = Простейшие факты В случае q = 2 расстояния по Хеммингу и по Ли совпадают: d = ρ, но вообще говоря это не так. Например, при q = 3: d(101, 221) = 2, ρ(101, 221) = |1 − 2| + |0 − 2| + |1 − 1| = 3. Легко видеть, что d(α̃, β̃) 6 ρ(α̃, β̃) для всех α̃, β̃. Дальше под расстоянием между наборами, если не указано иное, будем понимать расстояние Хемминга. r G α̃ = (α1 , . . . , αn ) ∈ Fnq ⇒ Br (α̃) = Sr (α̃) i=0   n |Sr (α̃)| = (q − 1)r r |Br (α̃)| = Простейшие факты В случае q = 2 расстояния по Хеммингу и по Ли совпадают: d = ρ, но вообще говоря это не так. Например, при q = 3: d(101, 221) = 2, ρ(101, 221) = |1 − 2| + |0 − 2| + |1 − 1| = 3. Легко видеть, что d(α̃, β̃) 6 ρ(α̃, β̃) для всех α̃, β̃. Дальше под расстоянием между наборами, если не указано иное, будем понимать расстояние Хемминга. r G α̃ = (α1 , . . . , αn ) ∈ Fnq ⇒ Br (α̃) = Sr (α̃) i=0   n |Sr (α̃)| = (q − 1)r r       n n n 2 |Br (α̃)| = 1 + (q − 1) + (q − 1) + . . . + (q − 1)r . 1 2 r Случай q = 2 Определение Множество Fn2 = {0, 1}n называется булевым кубом размерности n. Множество {0, 1}nk = {α̃ ∈ Fn2 : kα̃k = k} называется k-м слоем булева куба. Множество всех наборов из {0, 1}n , у которых фиксированы и одинаковы какие-то (n − k) разрядов, а остальные k разрядов произвольны, называется k-мерной гранью (подкубом) булева куба.   00010       00110 Пример: ∗0∗10 = — грань размерности 2.   10010     10110 Различные представления булева куба Куб {0, 1}n — это: линейно упорядоченное множество относительно лексикографического порядка (возрастание номера); частично упорядоченное множество относительно операции «6» покомпонентного сравнения наборов: если a = (a1 , . . . , an ) и b = (b1 , . . . , bn ), то a 6 b ⇐⇒ ∀ k : ak 6 bk , например, 0100 6 0111, а наборы 010 и 101 несравнимы; линейное векторное (нормированное) пространство; конечное поле F2n ; регулярный двудольный граф: его вершинами являются наборы куба, рёбрами соединяются соседние в смысле расстояния Хемминга вершины и только они. Индуктивное построение {0, 1}n−1 → {0, 1}n {0, 1}n−1 {0, 1}n−1 Индуктивное построение {0, 1}n−1 → {0, 1}n α̃1 α̃1 α̃k α̃k α̃2n−1 α̃2n−1 {0, 1}n−1 {0, 1}n−1 Индуктивное построение {0, 1}n−1 → {0, 1}n 0α̃1 1α̃1 0α̃k 1α̃k 0α̃2n−1 1α̃2n−1 {0, 1}n−1 {0, 1}n−1 Индуктивное построение {0, 1}n−1 → {0, 1}n 0α̃1 1α̃1 0α̃k 1α̃k 0α̃2n−1 1α̃2n−1 {0, 1}n−1 {0, 1}n−1 Индуктивное построение {0, 1}n−1 → {0, 1}n {0, 1}n 0α̃1 1α̃1 0α̃k 1α̃k 0α̃2n−1 1α̃2n−1 Булевы кубы малых размерностей 111 n=3 011 101 110 001 010 100 n=2 n=1 11 1 01 10 00 000 4-мерный куб 111 111 011 101 110 001 010 100 000 011 101 110 001 010 100 000 4-мерный куб 1111 0111 0011 0101 0110 0001 0010 0100 0000 1011 1101 1110 1001 1010 1100 1000 4-мерный куб 1111 0111 0011 0101 0110 0001 0010 0100 0000 1011 1101 1110 1001 1010 1100 1000 4-мерный куб 1111 0111 0011 0101 0110 0001 0010 0100 1011 1101 1110 1001 1010 1100 1000 сфера S1 (1001) 0000 4-мерный куб 1111 0111 0011 0101 0110 0001 0010 0100 1011 1101 1110 1001 1010 1100 1000 шар B1 (1001) 0000 4-мерный куб 1111 0111 0011 0101 0110 0001 0010 0100 1011 1101 1110 1001 1010 1100 1000 слой {0, 1}42 0000 4-мерный куб 1111 0111 0011 0101 0110 0001 0010 0100 1011 1101 1110 1001 1010 1100 1000 грань ∗101 0000 4-мерный куб 1111 0111 0011 0101 0110 0001 0010 0100 1011 1101 1110 1001 1010 1100 1000 грань ∗10∗ 0000 4-мерный куб 1111 0111 0011 0101 0110 0001 0010 0100 1011 1101 1110 1001 1010 1100 1000 грань ∗1∗∗ 0000 Куб {0, 1}5 Куб {0, 1}6 Куб {0, 1}7 Код и его минимальное расстояние Определение Произвольное подмножество C ⊆ Fnq называется кодом длины n над полем Fq , элементы x ∈ C — кодовые слова. Кодовое (минимальное) расстояние кода C: d(C) = min d(a, b). a,b∈C a6=b Пример У кода C = n 0010 o 1001 кодовое расстояние равно двум: d(C) = 2. 1100 Исправление и обнаружение ошибок Существует два взаимодополняющих метода борьбы с помехами: Кодирование с исправлением ошибок — декодер обнаруживает и исправляет ошибки. Кодирование с обнаружением ошибок — декодер распознаёт ошибки и в случае необходимости производит запрос на повторную передачу ошибочного блока. Задача теории помехоустойчивого кодирования: для каждого конкретного канала выбрать наиболее эффективный метод обнаружения и исправления ошибок. Исправление и обнаружение ошибок Определение Код C ⊆ Fnq обнаруживает s ошибок, если для каждого кодового слова x ∈ C при условии, что при передаче по каналу произвольно изменилось не более s разрядов из слова x, можно однозначно указать на наличие ошибок при передаче x. Код C исправляет t ошибок, если для всякого x ∈ C при условии, что канал связи изменил не более t разрядов слова x, можно по принятому слову y = x + e однозначно восстановить исходное слово x и определить ошибки e. Если код C исправляет t ошибок и при этом одновременно обнаруживает s 0 ошибок, то будем говорить, что код C обнаруживает s 0 ошибок в режиме исправления. Геометрическая интерпретация корректирующих свойств Непосредственно из определения кода, исправляющего t ошибок, следует, что шары радиуса t с центрами в кодовых словах не пересекаются. Значит, d(xi , xj ) > 2t для всех пар различных кодовых слов xi 6= xj и, таким образом, справедливо Утверждение Если код C исправляет t ошибок, то d(C) > 2t + 1. Замечание Начиная с этого момента символы t, s, s 0 будут обозначать наибольшее количество ошибок, исправляемых или распознаваемых кодом. Обозначения n и d зарезервируем за длиной и кодовым расстоянием. Код, исправляющий t ошибок x1 x2 t Исправимая ошибка y x1 x2 Неисправимая, но обнаружимая ошибка x1 x2 y Неустранимая ошибка x1 x2 = y Пример с нечётным d(C) x1 d =5 ⇒ t= x2 Пример с нечётным d(C) x1 d = 5 ⇒ t = 2, s = x2 Пример с нечётным d(C) x1 d = 5 ⇒ t = 2, s = 4, s 0 = x2 Пример с нечётным d(C) x1 x2 d = 5 ⇒ t = 2, s = 4, s 0 = 2 Пример с чётным d(C) x1 x2 d =6 ⇒ t= Пример с чётным d(C) x1 x2 d = 6 ⇒ t = 2, s = Пример с чётным d(C) x1 x2 d = 6 ⇒ t = 2, s = 5, s 0 = Пример с чётным d(C) x1 x2 d = 6 ⇒ t = 2, s = 5, s 0 = 3 Вычисление t, s, s 0 по d Кодовое расстояние однозначно характеризует корректирующие способности кода. Утверждение Для произвольного кода C с кодовым расстоянием d = d(C) справедливо:     d −1 d −1 , s = d − 1, s = s − t = . t= 2 2 Пример: код с повторением ( Ψ: 0 → 000 1 → 111 Используем эту схему кодирования в ДСК с p = 1 100 . Декодирование: принимается тот символ, который чаще встречается в принятом слове, например 100 0, 101 1. Вероятность ошибки Pош при передаче 1 бита при кодировании Ψ:   3 2 Pош = p (1 − p) + p 3 = 3p 2 − 2p 3 < 3 · 10−4 . 2 Pош уменьшилась более чем в 30 раз, но скорость передачи снижена в 3 раза, Основной вопрос Упражнение Для ∀ε > 0 и ∀m ∈ N любую двоичную последовательность i длины m можно передать по ДСК(p), p 6= 21 так, что получатель сможет определить посланную последовательность i с вероятностью > 1 − ε. Указание: использовать код с повторением. Вопрос Какой максимальной скорости передачи можно достичь в ДСК(p) при надёжности > 1 − ε? Теорема Шеннона Рассмотрим ДСК(p). Пропускная способность: C (p) = 1 − H(p) Для произвольных 1 p 6= , R < C (p), ε > 0 2 1 C (p) p Теорема (Шеннон, 1948) 1 2 1 существует блочный код с длиной n = n(ε) → ∞ и скоростью R, с помощью которого информация может быть передана по зашумлённому каналу с вероятностью ошибки декодирования, меньшей ε. Теорема Шеннона Рассмотрим ДСК(p). Пропускная способность: C (p) = 1 − H(p) Для произвольных 1 p 6= , R < C (p), ε > 0 2 1 C (p) p Теорема (Шеннон, 1948) 1 2 1 существует блочный код с длиной n = n(ε) → ∞ и скоростью R, с помощью которого информация может быть передана по зашумлённому каналу с вероятностью ошибки декодирования, меньшей ε. Обратная теорема Смысл термина «пропускная способность канала» раскрывает вторая теорема Шеннона: Теорема (обратная теорема Шеннона о кодировании) При всяком R > C (p) не существует никакого метода кодирования, позволяющего вести передачу по ДСК(p) со скоростью R и со сколь угодно малой вероятностью ошибки декодирования. Замечание Для других каналов связи с помехами также справедливы теоремы, аналогичные прямой и обратной теоремам Шеннона для ДСК(p), но только при иных энтропии канала H(p) и его пропускной способности C (p) = 1 − H(p). Основная литература Берлекэмп Э. Алгебраическая теория кодирования. — М.: Мир, 1971. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986. Вернер М. Основы кодирования. Учебник для ВУЗов. — М.: Техносфера, 2004. Лидл Р., Нидеррайтер Г. Конечные поля: в 2-х т. — М.: Мир, 1988. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. Дополнительная литература Аршинов М. Н., Садовский Л. Е. Коды и математика (рассказы о кодировании). — М.: Наука, 1983. Галлагер Р. Теория информации и надёжная связь. — М.: Сов. Радио, 1974. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования: методы, алгоритмы, применение. — М.: Техносфера, 2005. Шеннон К. Работы по теории информации и кибернетике. — М.: ИЛ, 1963. Яглом А. М., Яглом И. М. Вероятность и информация. — М.: Наука, 1973. Соловьева Ф. И. Введение в теорию кодирования (2006) http://www.codingtheory.gorodok.net/literature Sudan M. «Essential Coding Theory» — MIT Course № 6.896 http://theory.lcs.mit.edu/ madhu/FT02/ Домашнее задание 1 2 Доказать, что расстояние между двоичными векторами чётного веса чётно. Доказать, что если α̃, β̃ ∈ Fn2 , то ρ(α̃, β̃) = kα̃ ⊕ β̃k. 3 Слой наибольшей мощности среди всех слоёв булева куба называется средним слоем. Доказать, что последовательность |{0, 1}nk | при постоянном n и k = 0, 1 . . . n сначала возрастает, а затем убывает. Также показать, что в кубе чётной размерности имеется всего один средний слой, а в кубе нечётной размерности — два. 4 Доказать, что каждый из пяти приведённых в тексте примеров метрических пространств действительно является таковым. Какое отношение последний пример ρ(X , Y ) = |X 4 Y | имеет к метрике Хемминга? ? Вопросы ?