Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 29
Текст из файла (страница 29)
Пусть p — простое нечетное число. Определим дляэлемента a поля вычетов GF (pm ) символ Лежандра χ(a) как0, если a = 0, как +1, если уравнение x2 = a имеет решение вполе GF (pm ), и как −1 в противном случае. Доказатьа) χ(a)χ(b) = χ(ab);б) если pm ≡ 1 (mod 4), то χ(−1) = 1; если pm ≡ −1 (mod 4),то χ(−1)P = −1;в) a∈GF (pm ) χ(a) = 0;Pг) для любого b 6= 0 выполнено a∈GF (pm ) χ(a)χ(a + b) == −1.3.53*. Матрица Адамара H порядка n состоит из элементов±1 и удовлетворяет условиюHH T = nI,где I — единичная матрица.Построить матрицу Адамара порядка n = pm + 1, где p —простое, а n делится на 4.Глава 4Коды, исправляющие ошибки4.1.
Основная задача теориикодированияПусть есть набор сообщений Si , 1 6 i 6 n, которые нужно передавать по каналу связи. Сообщения будем кодироватьнулями и единицами, т. е. каждому сообщению будем сопоставлять его код — слово из нулей и единиц (бинарный набор),который обычно называется кодовым словом. Мы ограничимся только случаем, когда все сообщения кодируются словамиодинаковой длины. Будем считать, что ошибки при передачемогут только изменять значения некоторых битов.
Вообще говоря, это не единственный вид ошибок. Возможны, например,выпадения и вставки — какой-то из битов может не дойти доприемника или, наоборот, из-за помех может произойти ложное срабатывание приемника и получится бит, которого никто не посылал. Мы такие ситуации рассматривать не будем.Задача состоит в том, чтобы построить код минимальнойдлины, при передаче с помощью которого сообщение можетбыть однозначно восстановлено при условии, что произошлоне более r ошибок.Более удобно рассматривать другую задачу: даны n — длина кода, r — максимально допустимое число ошибок. Требуется найти максимальное число сообщений k, которое можнопередать.
Решив задачу про максимальное число сообщений,нетрудно получить решение и решение предыдущей задачипро код минимальной длины.170Глава 4.Коды, исправляющие ошибкиМы приближенно решим эту задачу для произвольных nи r. Точное решение будет дано лишь для случая n = 2m − 1и r = 1, а также для n = 23, r = 3 (см. раздел 4.5). Введемрасстояние между бинарными наборамиρ(α̃, β̃) =nXi=1|αi − βi |,где α̃ = (α1 , . . .
, αn ), β̃ = (β1 , . . . , βn ), αi , βi ∈ {0, 1}. (Эторасстояние часто называется метрикой Хэмминга.)Говоря попросту, ρ(α̃, β̃) — это число координат, по которым различаются наборы α̃ и β̃.Введем еще одно определение: норма kγ̃k — это число единичных координат в γ̃.Читателю предлагается самостоятельно проверить справедливость следующего простого утверждения.Утверждение 4.1. ρ(α̃, β̃) = kα̃ ⊕ β̃k, гдеα̃ ⊕ β̃ = (α1 + β1 ) mod 2, . . .
, (αn + βn ) mod 2 .Пример 4.2. α̃ = (101011), β̃ = (000110), ρ(α̃, β̃) = 4, α̃ ⊕ β̃ == (101101), kα̃ ⊕ β̃k = 4.Бо́льшая часть теории кодирования построена на так называемых групповых кодах, т. е. кодах, образующих группу (ихтакже называют линейными кодами).
Другими словами, множество кодовых слов {α̃1 , . . . , α̃q } образует группу относительно операции ⊕: для любых кодовых слов α̃i , α̃j выполняетсяα̃i ⊕ α̃j = α̃t , 1 6 t 6 q (достаточно проверить это утверждение,так как наличие обратного здесь очевидно — это сам элемент).Теорема 4.3. Предположим, что мы имеем групповой код{α̃1 , . . . , α̃q } относительно операции ⊕ (здесь и далее рассматриваются группы только относительно операции ⊕).Для минимального расстояния между различными кодовымисловами выполняется соотношение:min ρ(α̃i , α̃j ) = min kαt k.i6=jα̃t 6=0̃4.1.Основная задача теории кодирования171Доказательство.
ρ(α̃i , α̃j ) = kα̃i ⊕ α̃j k = kα̃u k, причемα̃u 6= (0, . . . , 0) при α̃i 6= α̃j . Отсюда получаем оценкуmin ρ(α̃i , α̃j ) > min kαt k.i6=jα̃t 6=0̃Ясно, что эта оценка достигается: набор (0, . . . , 0) обязательнопринадлежит групповому коду, а kα̃u k = kα̃u ⊕ 0̃k = ρ(α̃u , 0̃).Пусть передавалось сообщениеα̃i = (α1i , . . .
, αni ),а получено сообщениеβ̃ i = (β1i , . . . , βni ).Мы предположили, что число ошибок не больше r. Поэтомуρ(α̃i , β̃ i ) 6 r.Определение 4.4. Минимальное расстояние между кодовыми словами кода C называется кодовым расстоянием C.Совокупность таких β̃ i , что ρ(α̃i , β̃ i ) 6 r назовем шаромХэмминга Sr (α̃i ) с центром в α̃i и радиусом r.Утверждение 4.5. Множество {α̃1 , . . . , α̃q } образует код сисправлением ошибок, если Sr (α̃i ) ∩ Sr (α̃j ) = ∅ при i 6= j.Доказательство. Если при передаче сообщения α̃i сделаноне более r ошибок, то набор останется в шаре Sr (α̃i ). Еслишары не пересекаются, то мы можем однозначно восстановитьцентр шара по любой точке из этого шара.Отсюда следует, что у кода, исправляющего r ошибок, кодовое расстояние не меньше 2r + 1.Итак, чтобы построить код максимального размера, исправляющий r ошибок, нужно вложить в множество всех бинарных наборов E n (булев куб ) максимальное число непересекающихся шаров Хэмминга радиуса r.
В случае n = 2m − 1,r = 1 можно так расположить шары, чтобы они покрываликуб E n и не пересекались. Ясно, что такой код имеет самыйбольшой размер. Интересен вопрос, при каких других n и rможно разбиение E n на шары радиуса r. Оказывается, такоевозможно лишь еще при одной паре n и r: n = 23, r = 3(см. раздел 4.5).172Глава 4.Коды, исправляющие ошибкиТеорема 4.6 (теорема Хэмминга).
При 2r < n максимальное число сообщений k находится в следующих пределахn0+n12n+ ... +n2r 6k6n0+2n+ ...+n1 .nrДоказательство. Подсчитаем, сколько точек попадает в шаррадиуса r — это сам центр, все точки с одной измененной координатой (которую можно выбрать n1 способами), все точкис двумяизмененными координатами (которые можно выбратьn2 способами), . . . , все точки с r измененными координатами(их можно выбрать nr способами).
Так как шары не пересекаются, получаем верхнюю оценку.Для оценки снизу построим пример кода (негруппового).Берем произвольную точку α̃1 и строим вокруг нее шар радиуса 2r. В качестве следующей точки берем произвольнуюточку вне этого шара α̃2 и строим снова около нее шар радиуса 2r. Третью точку выберем вне этих двух шаров.
Далееаналогично. Заметьте, что каждый новый шар занимает неболее, чем nnn++ ...+012rточек. Значит, число таких шаров будет не меньшеn0+n12n+ ... +n2r.Очевидно, что шары радиуса r с центрами в построенныхточках не пересекаются, так как в построении использовалисьшары радиуса 2r.Теперь разберем случай n = 2m − 1, r = 1.Покажем, что2n,n+1т. е. при таких значениях параметров верхняя оценка в теоремеХэмминга достигается.Вначале построим код, а потом определим его кодовое расстояние.k=4.1.173Основная задача теории кодированияРассмотрим такую таблицу:100 . . .010 .
. .001 . . ..........000 . . .000 . . .000 . . ........... . . 000. . . 000. . . 000.... . . 100. . . 010. . . 0011100 . . . 0001010 . . . 0001001 . . . 0001111 . . . 1011111 . . . 1101111 . . . 111Справа выписываются все бинарные наборы длины m, содержащие более одной единичной координаты. Слева — единичная матрица размера (2m −(m+1))×(2m −(m+1)). Рассмотрим множество наборов (оно называется кодом Хэмминга),которые получаются при суммировании строчек этой таблицыmвсеми возможными способами. В этом множестве 22 −(m+1)наборов (результаты сложения различны для любого множества строчек).
Заметим, чтоm22m −(m+1)22 −12n==.2mn+1Найдем минимальное ρ(α̃i , α̃j ). Легко видеть, что ρ > 3,так как норма любого ненулевого набора, получаемого суммированием строчек таблицы, не меньше трех: если суммируемне менее трех строчек, то в левой части будет не менее трехединиц; если суммируем две строчки, то в левой части будетдве единицы, а в правой (наборы разные) — хотя бы одна;в любой строчке таблицы также содержится не менее трехединиц.Раз расстояния между кодовыми наборами не меньше трех,шары радиуса 1 с центрами в этих наборах не пересекаются.Пример 4.7.
Составим таблицу для кода Хэмминга длины 7:1000010000100001110101111011Складываем строчки произвольным образом и получаем 16возможных комбинаций. Ими можно закодировать 16 сообщений, например, все 10 цифр и знаки операций. При передаче с174Глава 4.Коды, исправляющие ошибкипомощью кода Хэмминга можно исправить одну ошибку, возникающую при передаче.4.2. Циклические кодыОдной из самых важных конструкций кодов являются циклические коды.Определение 4.8. Код C называется циклическим, если онинвариантен относительно циклических сдвигов: из того, чтонабор (α0 , .
. . , αn−1 ) принадлежит C, следует, что и всякийнабор (αs , αs+1 , . . . , αn−1 , α0 , . . . , αs−1 ) принадлежит C.По теореме 3.54 циклические линейные коды совпадают сидеалами в кольце F2 [x]/(xn − 1). Поэтому построить циклический код можно так: возьмем многочлен xn − 1, выберемнекоторый делитель ϕ(x) этого многочлена и в кольце вычетов по модулю xn − 1 рассмотрим идеал, порожденный ϕ(x).Оказывается, что при удачном выборе ϕ(x) коэффициентымногочленов, принадлежащих этому идеалу, будут давать хороший код.Давайте рассмотрим простой пример.Пример 4.9.
Пусть n = 7. Запишем разложение на неприводимые множители:x7 − 1 = (1 + x)(1 + x2 + x3 )(1 + x + x3 ).В качестве ϕ возьмем последний множитель. Умножая его настепени x получим базис в подпространстве, которое являетсякодом:(1101000)ϕ(0110100)ϕ·x(0011010)(0001101)ϕ · x2ϕ · x3Можно проверить, что кодовое расстояние для этого кода равно 3.В самом деле, умножение на x в кольце вычетов по модулюx7 − 1 приводит к циклическому сдвигу коэффициентов. Если4.3.Коды БЧХ175есть набор коэффициентов с двумя единицами, то расстояниемежду единицами в наборе не больше 2 (либо в одну сторону,либо в другую). Но тогда есть такой циклический сдвиг этогонабора, у которого единицы помещаются в младшей (левойполовине).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
