Информатика · объяснение и практика

Ближайшее кодовое слово и гарантированное исправление — разные утверждения

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Безопасность и надёжность данных · Учебная карта

Главная мысль

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

Метод и постановка

Зафиксируйте поле GF(2): сложение выполняется операцией XOR. Независимость строк проверяется именно над этим полем, а не привычным вещественным исключением. Если k строк независимы, их двоичные комбинации дают ровно 2^k различных слов. Повторение слова при разных комбинациях означает зависимость и несоответствие заявленной размерности.

Расстояние Хэмминга считает позиции, в которых два слова различаются. Для линейного кода разность двух кодовых слов опять принадлежит коду, поэтому достаточно найти минимальный вес среди ненулевых слов. Полный попарный подсчёт расстояний служит независимой проверкой на небольшом размере. Нулевое слово нельзя включать в минимум: иначе любой код ошибочно получил бы расстояние ноль.

Проверка и границы вывода

Гарантированный радиус исправления равен целой части (d−1)/2. Внутри этого радиуса шары вокруг разных слов не пересекаются. За пределом гарантии иногда всё ещё находится единственный ближайший вариант, но это свойство данного принятого слова, а не общее обещание восстановить исходное сообщение при произвольных ошибках.

Сравните принятое слово со всеми кодовыми словами и сохраните все варианты минимального расстояния. Ничья должна быть видна пользователю. Выбор первого элемента списка не устраняет неопределённость канала. Порождающая матрица также задаёт соответствие информационных комбинаций кодовым словам; одно восстановленное слово без этого соответствия ещё не сообщает исходные информационные биты. Инструмент ограничен малыми матрицами, поскольку полное перечисление растёт экспоненциально с размерностью.

Пример

Для единственной порождающей строки 111 код состоит из 000 и 111. Его расстояние равно трём, гарантируется исправление одной ошибки. Слово 101 находится на расстоянии один от 111 и два от 000.

Ближайший вариант здесь единственный: 111. В коде с порождающими строками 101 и 011 расстояние всего два; принятое 100 равноудалено от трёх кодовых слов, и честный результат должен перечислить ничью.

От чтения к действию

А теперь — вы

Код имеет минимальное расстояние четыре. Сколько ошибок гарантированно исправляется?

Частые вопросы

Ближайшее слово обязательно было отправлено?

Нет. При числе ошибок вне гарантированного радиуса близость сама по себе не доказывает исходное слово.

Что если ближайших слов несколько?

Все такие слова перечисляются; произвольный выбор одного скрывал бы неоднозначность.

Углублённый разбор

Восстановление стираний по рангу проверочных столбцов

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

Перед началом: Линейный код как ядро; Ранг над конечным полем.

Потерянные позиции становятся неизвестными системы

Пусть C={c:Hc=0} над F_q. Разобьём координаты на стёртые E и известные K. Тогда неизвестный вектор u обязан удовлетворять H_Eu=−H_Kc_K. Справа стоит вычислимый синдром известных символов. Если система несовместна, одних стираний недостаточно для объяснения полученных данных: среди якобы известных символов есть ошибка либо модель кода неверна.

При совместности множество решений является аффинным сдвигом ker H_E. Поэтому число допустимых заполнений равно q^{|E|−rank H_E}. Единственность равносильна полному столбцовому рангу H_E. Полный строковый ранг всей H этого не гарантирует: нужная подматрица может содержать зависимые столбцы, даже если все проверки кода независимы.

Минимальное расстояние даёт гарантию для всех расположений

Если существует ненулевой кодовый вектор, поддержка которого целиком лежит в E, его можно прибавить к любому заполнению, не меняя известные координаты. Это ровно ненулевой элемент ядра H_E. Следовательно, конкретный набор стираний восстановим тогда и только тогда, когда он не содержит поддержку ненулевого кодового слова.

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

Проверяйте кандидата по исходной матрице

После решения подставьте все восстановленные символы в полный вектор и проверьте Hc=0. Затем отдельно убедитесь в совпадении известных координат. Проверка только нулевого синдрома способна принять другое кодовое слово, которое противоречит полученным данным. Проверка только известных координат, наоборот, ничего не говорит о соблюдении кода.

При двоичных данных исключение Гаусса использует XOR, а не вещественное деление. Численный ранг над вещественными числами может отличаться от ранга над F₂. Если ответов несколько, лучше вернуть параметризацию или список, а не произвольно выбрать один и назвать его гарантированно восстановленным сообщением.

Два стирания с разным исходом

Условие. Над F₂ задана H со строками (1,0,1,1) и (0,1,1,0). Сравните E={1,2} при c₃=1,c₄=0 и E={1,4} при c₂=c₃=0.

  1. В первом случае проверки дают u₁⊕1=0 и u₂⊕1=0. Единственное заполнение имеет u₁=u₂=1, то есть слово 1110.
  2. Выбранные столбцы 1 и 2 образуют единичную матрицу. Их ранг два объясняет единственность независимо от конкретной совместной правой части.
  3. Во втором случае остаётся одно независимое уравнение u₁⊕u₄=0. Столбцы 1 и 4 совпадают, и их ранг равен одному.
  4. Допустимы слова 0000 и 1001. Полный код состоит из 0000,1001,1110,0111, так что его расстояние равно двум; это не мешает первому частному восстановлению двух стираний.

Ответ. Первый набор даёт единственное 1110; второй даёт два заполнения.

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

Где легко ошибиться. Не считайте все наборы одинаковой мощности одинаково восстановимыми. Решающим является ранг выбранных столбцов над полем кода.

Проверьте понимание

Сколько заполнений у второго набора стираний?

Вопросы к этой главе

Стирание легче неизвестной ошибки?

Да: позиция повреждения уже известна. Для стираний решается система на этих позициях; при неизвестных ошибках нужно дополнительно определить их расположение.

Зависимые строки H портят критерий?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • SageMath: linear codes, parity_check_matrix

    Прочитано определение проверочной матрицы как генератора двойственного кода. Критерий стираний доказан через ядро выбранных столбцов; собственная матрица и два набора позиций перебраны отдельно.

Граница Синглтона для параметров кода

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

Перед началом: Расстояние Хэмминга; Размер линейного кода.

Удаление координат должно оставаться инъективным

Пусть код длины n над алфавитом размера q имеет M слов и минимальное расстояние d. Удалим любые d−1 координат у каждого слова. Если две укороченные записи совпали, исходные слова различались только в удалённых позициях, то есть на расстоянии не больше d−1. Это противоречит определению d. Значит, отображение на оставшиеся координаты инъективно.

В оставшихся n−d+1 позициях существует всего q^{n−d+1} различных записей. Поэтому M≤q^{n−d+1}. Линейность для этого рассуждения не нужна. Если код линейный размерности k над F_q, его мощность равна qᵏ, и после сравнения степеней получается d≤n−k+1. Это ограничение на параметры любого уже существующего кода.

Равенство требует отдельной конструкции

Код, достигающий равенства, называют MDS. Само неравенство не доказывает существование такого кода для каждого алфавита и набора n,k. Сначала нужно предъявить код и проверить его расстояние. Замена размера поля может изменить возможность конструкции, хотя правая часть n−k+1 останется прежней.

В линейном коде достаточно искать минимальный вес ненулевого слова: расстояние двух слов равно весу их разности, которая также принадлежит коду. Но размерность генераторной матрицы нужно проверить отдельно. Если строки зависимы, запись из k строк ещё не означает мощность qᵏ и подстановка такого k даст неверную оценку.

Равенство означает восстановимость по оставшимся координатам

При M=q^{n−d+1} инъективная проекция на любые n−d+1 координат становится биекцией на весь набор возможных записей. Следовательно, любые k координат линейного MDS кода однозначно определяют слово. Это объясняет связь границы с восстановлением стираний, но не превращает её в алгоритм исправления неизвестных ошибок.

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

Девять троичных слов

Условие. Над F₃ задан код c(a,b)=(a,b,a+b,a+2b), где a,b пробегают 0,1,2. Найдите параметры и сравните с границей Синглтона.

  1. Первые две координаты сохраняют сообщение, поэтому отображение инъективно. Слов девять, размерность равна двум, длина равна четырём.
  2. Для ненулевой пары (a,b) ровно одно из четырёх выражений a,b,a+b,a+2b равно нулю. Две нулевые координаты дали бы независимые уравнения и вынудили a=b=0.
  3. Поэтому каждое из восьми ненулевых слов имеет вес три. Минимальное расстояние линейного кода равно трём.
  4. Граница даёт d≤4−2+1=3. Достигнуто равенство; любая пара координат различает все девять сообщений и позволяет восстановить остальные.

Ответ. Получен троичный [4,2,3] код, достигающий границы Синглтона.

Проверка. Перебор девяти сообщений подтверждает распределение весов 1+8z³; все шесть двухкоординатных проекций имеют девять различных образов.

Где легко ошибиться. Верхняя граница расстояния не является обещанием существования кода с равенством. Алфавит, размерность и реальная конструкция требуют собственной проверки.

Проверьте понимание

Какова граница на d при n=4,k=2?

Вопросы к этой главе

Можно удалить любые d координат?

Доказательство гарантирует инъективность только после удаления d−1. При удалении всей поддержки минимального ненулевого слова оно склеится с нулевым словом.

Почему код над F₃, а не над целыми?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • SageMath: singleton_upper_bound

    Прочитаны граница мощности q^(n-d+1) и термин MDS. Доказательство через инъективное удаление координат изложено самостоятельно; собственный троичный код проверен перебором девяти слов.

Декодирование Рида — Соломона через локатор ошибки

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

Перед началом: Интерполяция над полем; Линейная система.

Две группы коэффициентов заменяют неизвестный набор ошибок

Пусть различные точки x₁,…,xₙ принадлежат конечному полю, а передаваемый многочлен f имеет степень<k. В полученных yᵢ испорчено не больше e значений. Берём ненулевой монический E степени e, содержащий множители x−xᵢ для всех ошибок, и Q=fE степени<k+e. Тогда для каждой точки Q(xᵢ)=yᵢE(xᵢ): на правильных данных равенство обычное, на ошибочных обе стороны нулевые.

Если ошибок меньше e, локатор можно дополнить любым моническим множителем нужной степени; его дополнительные корни не обязаны означать реальные ошибки. Зафиксировав старший коэффициент E равным 1, получаем линейную систему по оставшимся коэффициентам E и всем коэффициентам Q. Условие моничности исключает бесполезное нулевое решение и снимает общую масштабную неоднозначность пары.

Достаточно корней, чтобы доказать правильное деление

Предположим n≥k+2e и правильный f существует. Для любого решения системы многочлен Q−fE имеет степень<k+e и обращается в нуль минимум в n−e≥k+e правильных точках. Поэтому он тождественно нулевой. Значит любой найденный E≠0 даёт то же отношение Q/E=f, даже если сам локатор не единственен.

После решения системы нужно действительно разделить Q на E без остатка, проверить степень частного<k и количество несовпадений с y не больше e. Если условий нет или данные выходят за модель, алгоритм может отказать; нельзя объявлять произвольную рациональную функцию восстановленным сообщением. Коэффициенты и деление вычисляются в заданном поле, поэтому целочисленные отрицательные числа нормируются по модулю.

Исправление отличается от гарантии ближайшего слова

На указанном радиусе декодируемое сообщение единственно: два многочлена степени<k, каждый с не больше e ошибками, совпали бы минимум в n−2e≥k точках и потому были бы равны. При большем радиусе похожая линейная конструкция без дополнительных проверок не обещает ни существования, ни единственности. Отдельный перебор всех маленьких сообщений удобен как независимый оракул, но сам метод не требует такого экспоненциального поиска.

Одна испорченная оценка над F₇

Условие. Точки 0,1,2,3,4 имеют полученные значения 2,5,6,4,0 в F₇. Ищите f степени<2 с не больше одной ошибкой методом Q,E.

  1. Берём E=x+e₀ и Q=q₀+q₁x+q₂x². Пять уравнений записываются q₀+q₁xᵢ+q₂xᵢ²−yᵢe₀=yᵢxᵢ modulo7.
  2. Решение системы даёт e₀=5 и q₀=q₁=q₂=3. Значит E=x+5=x−2, Q=3x²+3x+3.
  3. Точное деление даёт Q/E=3x+2, поскольку (x+5)(3x+2)=3x²+3x+3 modulo7.
  4. Его значения равны 2,5,1,4,0. Только координата x=2 отличается от полученной 6; локатор действительно там нулевой. Условие 5≥2+2·1 выполнено.

Ответ. Восстановлено f(x)=2+3x; исправление y(2):6→1.

Проверка. Независимый перебор 49 линейных многочленов F₇ находит единственный с расстоянием≤1 до полученного вектора. Все пять линейных уравнений и произведение Q=fE проверены отдельно по коэффициентам.

Где легко ошибиться. Не считайте каждый корень дополненного локатора настоящей ошибкой и не пропускайте проверку делимости Q на E. Восстанавливаемый объект должен быть многочленом нужной степени.

Проверьте понимание

Какой многочлен восстановлен для указанного вектора над F₇?

Вопросы к этой главе

Почему не требуется знать ошибочную позицию заранее?

Она кодируется коэффициентами E, которые входят в общую линейную систему. Нуль локатора делает неверное yᵢ безвредным в уравнении, а правильные точки связывают отношение Q/E.

Почему пять уравнений для четырёх неизвестных не мешают?

Система может быть переопределённой, но согласованной, если модель ошибок соблюдена. Число уравнений не обязано равняться числу неизвестных; лишняя точка даёт дополнительный контроль правильности данных.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Larry Guth: The Berlekamp–Welch Algorithm, §1

    Прочитаны vanishing lemma и линейное условие R₀(x)+R₁(x)y=0 на повреждённых данных. Источник рассматривает особый режим полного поля; наша граница n≥k+2e выведена отдельно. В последней дроби PDF есть переставленные R₀/R₁: здесь Q/E сверено делением и всеми исходными точками. RutgersURL inaccessible, два StanfordPDF timeout; они не считаются прочитанными.

Циклический код как идеал факторкольца

Линейный код, замкнутый относительно циклического сдвига, имеет более жёсткую алгебраическую структуру. Его слова являются кратными одного делителя xⁿ−1 в факторкольце. Степень генератора сразу задаёт размерность, а умножение на x объясняет сдвиг без потери старшего бита.

Перед началом: Полиномиальное деление; Линейный код.

Координаты становятся коэффициентами

Слову (c₀,…,cₙ₋₁) над полем F сопоставим c(x)=c₀+c₁x+…+cₙ₋₁xⁿ⁻¹. Работаем в R=F[x]/(xⁿ−1), где xⁿ=1. Умножение c на x с приведением по модулю отправляет последнюю координату в первую и сдвигает остальные вправо. Обычное отбрасывание старшего коэффициента вместо его возврата описывало бы другой, нециклический переход.

Если код линеен и замкнут по этому сдвигу, он замкнут по умножению на любую сумму степеней x, то есть на любой элемент R. Следовательно это идеал факторкольца. Обратно, идеал автоматически линеен над F и сохраняется при умножении на x, значит задаёт циклический линейный код. Здесь линейность является существенной частью соответствия, а не следствием одного лишь разрешения вращать отдельные слова.

Минимальный монический элемент порождает весь код

Прообраз идеала в F[x] содержит xⁿ−1. Поскольку F[x] — кольцо главных идеалов, он порождён единственным моническим g, делящим xⁿ−1. Все слова степени<n представляются как m(x)g(x), где deg m<n−deg g. Отображение m↦mg инъективно: ненулевой продукт имеет степень<n и не может исчезнуть после приведения. Поэтому размерность кода равна n−deg g.

Делимость g|(xⁿ−1) нужна для сохранения кратности при возврате старшей координаты. Произвольный многочлен, используемый как контрольная сумма при фиксированной передаче, не автоматически является генератором циклического кода выбранной длины. В нулевом коде можно взять g=xⁿ−1 и размерность 0; в полном коде g=1 и размерность n. Условие взаимной простоты n и характеристики поля для этого идеального описания не требуется.

Сдвиг проверяет структуру, расстояние требует другого анализа

Генератор и размерность не сообщают минимальное расстояние одним только названием. У одного и того же n,deg g могут быть разные весовые свойства. Для маленького кода можно перечислить все m и проверить замкнутость по сдвигу и сложению. Это отличается от вычисления одного CRC-остатка: здесь задаётся всё пространство слов конкретной длины, его базис и число сообщений, а не только обнаружение одной ошибки.

Шестикоординатный бинарный код

Условие. Над F₂ возьмите n=6 и g=x²+x+1. Проверьте делимость, размерность и циклический сдвиг слова с сообщением m=x³.

  1. Имеем (x²+x+1)(x⁴+x³+x+1)=x⁶+1=x⁶−1 в F₂. Поэтому g действительно задаёт циклический код длины 6.
  2. Степень g равна 2, значит размерность 4, сообщений и кодовых слов 2⁴=16. Базис образуют g,xg,x²g,x³g.
  3. Для m=x³ получаем c=x⁵+x⁴+x³. Умножаем на x и возвращаем x⁶ в1: сдвиг равен 1+x⁴+x⁵.
  4. Этот сдвиг снова кратен g: 1+x⁴+x⁵=(x³+x+1)g. Значит его новое сообщение имеет степень 3<4 и лежит в том же коде.

Ответ. Параметры длины/размерности: [6,4];16 слов; сдвиг x⁵+x⁴+x³ равен 1+x⁴+x⁵ и остаётся в коде.

Проверка. Полное перечисление 16 сообщений даёт 16 разных произведений. Их циклические сдвиги принадлежат тому же набору; независимое XOR-деление подтверждает два конкретных частных и нулевые остатки.

Где легко ошибиться. Не выбирайте g без проверки g|(xⁿ−1) для заданной длины и не теряйте старший коэффициент при циклическом сдвиге. Он возвращается в постоянный член.

Проверьте понимание

Какова размерность кода длины 6 с генератором степени 2?

Вопросы к этой главе

Почему число 2 делит n, но построение всё равно корректно?

В характеристике 2 многочлен x⁶−1 имеет повторные множители, однако описание идеала и формула размерности остаются верны. Дополнительные предположения нужны для некоторых теорем о корнях и BCH, которые здесь не применяются.

Равен ли вес генератора минимальному расстоянию?

Не обязательно. В этом коде g имеет вес 3, но (x+1)g=x³+1 имеет вес 2. Следовательно уже этот пример показывает, почему размерность и вес g не заменяют проверку минимального расстояния.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • J. I. Hall: Coding Theory, chapter8, Theorem8.1.1

    Прочитаны сдвиг как умножение на x modulo xⁿ−1, замкнутость по полиномиальным множителям и единственный monic generator делитель с размерностью n−deg g. Свой бинарный код длины 6 проверен 16 сообщениями; корневая классификация BCH не используется.

Весовой многочлен двойственного кода

Весовое распределение линейного кода определяет распределение его ортогонального кода. Тождество Мак-Вильямс заменяет перебор всех двойственных слов подстановкой в однородный многочлен. Нормировка размером исходного кода и линейность являются обязательными условиями.

Перед началом: Двойственный линейный код; Биномиальная формула.

Многочлен хранит число слов каждого веса

Для бинарного линейного C⊆F₂ⁿ определим W_C(x,y)=Σ_{c∈C}x^(n−wt(c))y^wt(c). Коэффициент при x^(n−j)yʲ равен числу слов веса j. Нулевое слово даёт xⁿ, а W_C(1,1)=|C|. Двойственный C⊥ состоит из векторов v, для которых c·v=0 modulo2 для каждого c∈C.

Тождество имеет вид W_{C⊥}(x,y)=W_C(x+y,x−y)/|C|. Оно переносит всё распределение сразу, но не восстанавливает конкретные координаты двойственных слов или генераторную матрицу. Знаки промежуточного раскрытия могут быть отрицательными, однако итоговые коэффициенты обязаны быть неотрицательными целыми. Нарушение этого контроля указывает на ошибку нормировки либо на неподходящую исходную гипотезу.

Ортогональность характеров объясняет подстановку

Для фиксированного v сумма Σ_{c∈C}(−1)^(c·v) равна |C|, если v∈C⊥. Иначе существует c₀∈C с c₀·v=1; замена c на c+c₀ попарно меняет знаки, и сумма равна 0. Линейность делает это сдвигом внутри того же множества. Поэтому индикатор двойственного условия равен этой сумме, делённой на |C|.

Подставим индикатор в сумму по всем v∈F₂ⁿ и поменяем порядок конечных сумм. Для координаты с cᵢ=0 получается множитель x+y, с cᵢ=1 — x−y. Для каждого c итог равен (x+y)^(n−wt(c))(x−y)^wt(c), что и даёт формулу. Доказательство одновременно объясняет, почему нельзя делить на2ⁿ вместо размера C и почему произвольный нелинейный набор слов требует другой постановки.

Размер и минимальный вес служат независимыми проверками

После преобразования сумма коэффициентов должна быть |C⊥|=2ⁿ/|C|. Свободная по y часть должна равняться xⁿ, поскольку нулевое слово единственно. Первый ненулевой весовой коэффициент после нулевого даёт минимальное расстояние линейного двойственного кода. На небольшом n эти результаты можно отдельно проверить решением ортогональных уравнений и перечислением всех допустимых векторов.

Из четырёх слов получаем распределение восьми

Условие. Бинарный C порождён векторами 11100 и00111. Найдите W_C и W_{C⊥}, в частности число двойственных слов веса 2.

  1. Исходные слова 00000,11100,00111,11011 имеют веса 0,3,3,4. Поэтому W_C=x⁵+2x²y³+xy⁴ и |C|=4.
  2. Подставляем x+y и x−y: W_{C⊥}=[(x+y)⁵+2(x+y)²(x−y)³+(x+y)(x−y)⁴]/4.
  3. После раскрытия получаем x⁵+2x³y²+4x²y³+xy⁴. Значит слов веса 2 ровно 2, веса 3 —4, веса 4 —1.
  4. Для независимой проверки двойственные уравнения: v₁+v₂+v₃=0 и v₃+v₄+v₅=0. Они имеют 8 решений; среди них веса 2 достигают 11000 и00011.

Ответ. W_{C⊥}=x⁵+2x³y²+4x²y³+xy⁴; слов веса 2 ровно 2.

Проверка. Полный перебор 32 бинарных векторов отбирает 8 ортогональных слов с распределением[1,0,2,4,1,0]. Сумма 8 равна 2⁵/4, а наименьший ненулевой вес двойственного кода равен 2.

Где легко ошибиться. Не пропускайте деление на |C| и не используйте размер двойственного кода вместо исходного в выбранном направлении формулы. Проверяйте целочисленность и сумму всех коэффициентов.

Проверьте понимание

Сколько слов веса 2 имеет двойственный код задачи?

Вопросы к этой главе

Почему исходный код имеет ровно 4 слова?

Два генератора линейно независимы: они ненулевые и различны, а над F₂ зависимость двух ненулевых векторов означала бы равенство. Поэтому размерность 2 и число слов 2².

Определяет ли многочлен сам код с точностью до координат?

Нет. Он хранит только количества по весам и забывает расположение единиц. Разные коды могут иметь одинаковое распределение; тождество переносит эту агрегированную информацию, не полную матрицу.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • J. I. Hall: Coding Theory, chapter9, Theorem9.1.1

    Прочитаны homogeneous weight enumerator и MacWilliams transformation. Свой пятикоординатный бинарный код, двойственное перечисление 8 слов и характерное доказательство проверены отдельно. UCIkaplancodingnotes.pdf вернул 502 и не использован.

Прокалывание и укорочение линейного кода — разные операции

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

Перед началом: Линейный двоичный код и порождающая матрица; Вес Хэмминга и размерность подпространства.

Проекция сохраняет все исходные слова

Прокалывание в координате i означает применить ко всем словам линейную проекцию, удаляющую эту координату. Разные исходные слова иногда сливаются. Ядро проекции внутри кода содержится в одномерном пространстве, порождённом единичным вектором e_i. Поэтому размерность уменьшается не более чем на 1 и остаётся прежней, если e_i не принадлежит коду.

Вес любого слова уменьшается на 0 или 1. Для кода с исходным расстоянием d≥2 проекция не сливает ненулевое слово с нулём, и расстояние проколотого кода находится между d−1 и d. При d=1 нужно отдельно учитывать возможное слияние: нельзя применять это рассуждение о ненулевых словах без проверки ядра.

Укорочение сначала вводит нулевое условие

Укорочение в той же координате сначала оставляет подкод C0={c∈C: c_i=0}, затем удаляет уже нулевую координату. Веса оставленных слов не меняются. Если координатный функционал ненулевой на C, условие уменьшает размерность на 1; если координата всегда нулевая, размерность сохраняется. На самом C0 последующее удаление инъективно.

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

Один пример разделяет две операции

Пусть строки порождающей матрицы равны 1101 и 0111. Код содержит 0000,1101,0111,1010 и имеет размерность 2, расстояние 2. Прокалываем первую координату: получаем 000,101,111,010. Слово 010 имеет вес 1, поэтому новое расстояние 1, а четыре различных слова сохраняют размерность 2.

Для укорочения сначала оставляем исходные 0000 и 0111 с нулевой первой координатой. После её удаления остаются 000 и 111: размерность 1, расстояние 3. Обе операции дали длину 3, но одинаковая длина не означает одинакового числа сообщений или одинаковой способности различать ошибки. В проверке удобно явно перечислить слова, чтобы не подменить отбор простой обрезкой матрицы.

Длина одинакова, параметры кода различаются

Условие. Над GF(2) код порождён строками 1101 и 0111. Сравните прокалывание и укорочение по первой координате: длину, размерность и минимальное расстояние.

  1. Линейная оболочка состоит из 0000,1101,0111,1010; ненулевые веса 3,3,2 дают исходные параметры[4,2,2].
  2. Проекция всех слов даёт 000,101,111,010. Это четыре слова длины 3, среди них есть вес 1: параметры[3,2,1].
  3. Нулевое условие на первую координату оставляет 0000 и 0111. Их проекция даёт 000,111 с параметрами[3,1,3].
  4. Проверка размерностей: log2(4)=2 и log2(2)=1. Укорочение сохранило веса оставленных слов, а прокалывание уменьшило вес 1010 с 2 до 1.

Ответ. Прокалывание: [3,2,1]. Укорочение: [3,1,3]. Это разные коды одной длины.

Проверка. Обратная вставка нулевой первой координаты восстанавливает оба укороченных слова. Для проколотого 010 исходный прообраз 1010 показывает, почему расстояние снизилось.

Где легко ошибиться. Не удаляйте координату до отбора нулевого подкода, если требуется именно укорочение.

Проверьте понимание

Сколько информационных битов осталось после укорочения в этом примере?

Вопросы к этой главе

Всегда ли прокалывание сохраняет размерность?

Нет. Если код содержит e_i, проекция уничтожает это ненулевое направление. В данном примере такого слова нет, поэтому размерность сохраняется.

Почему расстояние при укорочении может возрасти?

Отбор может исключить все исходные слова минимального веса. Координата удаляется только после отбора и у оставленных слов уже равна нулю.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • SageMath Coding Theory: punctured и shortened

    Определения проекции и нулевого подкода перед проекцией. Матрица, полный набор слов и сравнение параметров построены для этой главы; координаты в объяснении нумеруются с 1.

Граница Плоткина через сумму всех попарных расстояний

Большое расстояние между двоичными словами ограничивает число кодовых слов даже без линейности кода. Граница Плоткина получается двойным подсчётом: снизу суммируются обязательные расстояния между парами, сверху — возможные несовпадения в каждом столбце.

Перед началом: Расстояние Хэмминга; Подсчёт неупорядоченных пар.

Одна сумма имеет два описания

Пусть код C содержит M различных двоичных слов длины n, а расстояние любой пары не меньше d. Сумма S расстояний по всем неупорядоченным парам не меньше d·M(M−1)/2. Здесь не предполагается, что слова образуют линейное пространство или что M является степенью двойки. Используется лишь число пар и заданная нижняя граница расстояния.

Рассмотрим один столбец записи всех M слов. Если в нём k единиц и M−k нулей, этот столбец добавляет ровно k(M−k) несовпадающих пар. Максимум равен floor(M²/4) и достигается при наиболее равномерном разделении. Сложение по n столбцам даёт S≤n·floor(M²/4)≤nM²/4. Это верхняя оценка той же самой суммы, а не другого показателя кода.

Почему появляется порог n/2

Совмещая оценки и деля на положительное M, получаем (2d−n)M≤2d. Если d>n/2, коэффициент слева положителен и M≤floor(2d/(2d−n)). Чем ближе слова к взаимным противоположностям по расстоянию, тем меньше слов можно разместить. В применении к целому M округлять границу следует вниз, а не к ближайшему целому.

При d=n/2 делить на 2d−n нельзя. Полученное неравенство в этом виде уже не ограничивает M сверху; пограничный случай требует отдельного аргумента. Более точный исходный множитель floor(M²/4) иногда усиливает вывод для нечётного M. Однако даже строгая верхняя граница не обязана достигаться при любых n, d: возможность построения кода является отдельной задачей.

Когда пример удостоверяет точность границы

Для n=6 и d=4 оценка даёт M≤8/(8−6)=4. Четыре слова 000000,001111,110011,111100 имеют попарное расстояние 4. Значит, здесь верхняя граница достигается. Проверка конструкции обязательна: одно лишь вычисление числа 4 ещё не доказывало существование четырёх подходящих слов.

В каждом столбце этой конструкции две единицы и два нуля. Поэтому каждый столбец вносит 4 в сумму S, а шесть столбцов дают 24. Поскольку пар тоже шесть и каждая имеет расстояние 4, нижняя оценка также равна 24. Совпадение двух подсчётов объясняет точность результата и показывает, какую балансировку столбцов потребовало равенство в доказательстве.

Длина шесть и расстояние четыре

Условие. Найдите наибольшее возможное число двоичных слов длины 6 с минимальным расстоянием не меньше 4. Линейность кода заранее не предполагается.

  1. Для M слов нижняя оценка суммы расстояний равна 4·M(M−1)/2, верхняя —6M²/4.
  2. После упрощения(8−6)M≤8, поэтому M≤4.
  3. Проверяем набор 000000,001111,110011,111100: каждая из шести пар отличается в четырёх позициях.
  4. Полученная конструкция содержит 4 слова и достигает верхней границы. Следовательно, максимум равен 4, а не только ограничен этим числом.

Ответ. Максимум равен 4; это верно среди всех двоичных кодов, включая нелинейные.

Проверка. Двойной подсчёт на конструкции даёт S=6·4=24 по столбцам и S=6·4=24 по парам. Независимая проверка всех шести расстояний подтверждает минимальное расстояние 4.

Где легко ошибиться. Не требуйте от M быть степенью двойки при доказательстве верхней границы: это свойство линейного кода, а условие задачи допускает произвольный набор слов.

Проверьте понимание

Какое дополнительное условие на код использовано в доказательстве через k(M−k)?

Вопросы к этой главе

Доказывает ли неравенство существование кода указанного размера?

Нет. Оно даёт только верхнюю границу. Для точного максимума нужна конструкция или отдельное доказательство достижимости, как в разобранном примере из четырёх слов.

Почему расстояние ровно n/2 требует отдельного случая?

После двойного подсчёта коэффициент при M обращается в ноль. Деление на него недопустимо; полученная строгая форма границы относится именно к d>n/2.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • MIT6.895: границы расстояния и размера кода

    Лекция посвящена границе Плоткина и сравнению расстояния с числом кодовых слов. Строгая форма для d>n/2 здесь выведена отдельным подсчётом столбцов и проверена конструкцией длины 6.

Граница Хэмминга: непересекающиеся шары вокруг кодовых слов

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

Перед началом: Двоичное слово и расстояние Хэмминга; Биномиальные коэффициенты.

Сколько принятых слов обязан обслужить один центр

Двоичные блочные коды фиксированной длины; линейность не предполагается. Исправляются любые ошибки не более заданного веса.

У слова длины n имеется C(n,j) двоичных искажений ровно в j позициях: достаточно выбрать позиции, поскольку новый бит после переворота уже определён. Вместе с неискажённым словом шар радиуса t содержит V(n,t)=Σⱼ₌₀ᵗC(n,j) записей. Число не зависит от положения центра, и повторного подсчёта внутри одного шара нет.

Если минимальное расстояние d≥2t+1, два таких шара не пересекаются. Иначе промежуточная запись находилась бы не дальше t от каждого центра, а неравенство треугольника дало бы расстояние центров не больше 2t. При M центрах занято M·V(n,t) различных записей из всего пространства мощности 2ⁿ. Отсюда M·V(n,t)≤2ⁿ — граница Хэмминга.

Что означает свободное место между шарами

При заданном d выбирают t=⌊(d−1)/2⌋. Верхнюю границу на целое M округляют вниз. Для линейного двоичного кода M=2ᵏ, поэтому проверяют и это дополнительное ограничение: допустимый вещественный логарифм не является целой размерностью. Доказательство упаковки при этом одинаково для линейных и нелинейных кодов.

Равенство в упаковочной границе означает, что непересекающиеся шары покрыли все принятые слова; такой код называют совершенным для данного радиуса. Само равенство чисел не предъявляет нужные центры. При строгом неравенстве свободные записи тоже не обязаны позволять вставить ещё один центр: расположение уже занятых областей связано с геометрией двоичного пространства.

Чётность даёт дополнительный сертификат невозможности

Для M двоичных слов сумма расстояний по всем неупорядоченным парам равна Σᵢaᵢ(M−aᵢ), где aᵢ — число единиц в координате i. Каждая координата вносит ровно столько пар с различными битами. Это независимый способ ограничить сумму расстояний сверху, без перечисления всех шаров и без предположения о линейности.

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

Почему пять центров не помещаются при n=5,d≥3

Условие. Проверьте возможность двоичного кода длины пять из пяти слов с расстоянием не меньше трёх. Сначала примените упаковочную границу, затем используйте сумму попарных расстояний.

  1. Радиус исправления t=1. Один шар содержит C(5,0)+C(5,1)=6 записей, а всё пространство — 32. Граница даёт M≤⌊32/6⌋=5 и пока не отвергает M=5.
  2. Из пяти весов хотя бы три имеют одну чётность. Минимальное число пар одинаковой чётности получается при разделении 2+3: C(2,2)+C(3,2)=4 пары.
  3. Всего пар десять. Четыре из них имеют расстояние минимум четыре, остальные — минимум три. Поэтому сумма расстояний не меньше 4·4+6·3=34.
  4. В каждой из пяти координат число разделённых пар a(5−a) не превосходит шести. Вся сумма не больше 5·6=30. Неравенства 34≤сумма≤30 противоречат друг другу.
  5. Набор из четырёх слов 00000,11100,10011,01111 действительно имеет минимальное расстояние три. Значит, в этом небольшом случае достижимо четыре, хотя сама упаковка допускала пять.

Ответ. Код из пяти слов невозможен. Упаковочная граница даёт только M≤5; дополнительный аргумент снижает достижимую мощность до четырёх.

Проверка. Шесть расстояний предъявленного четырёхсловного кода равны 3,3,4,4,3,3. Верхняя оценка 30 для гипотетических пяти слов получена по координатам, а нижняя 34 — по парам; это разные подсчёты одной величины.

Где легко ошибиться. Не заменяйте условие M·V≤2ⁿ утверждением «код существует». Также не включайте в радиус t=⌊d/2⌋ при чётном d: шары такого радиуса уже могут пересекаться.

Проверьте понимание

Какую верхнюю границу на M даёт именно упаковка шаров при n=5,d=3, до дополнительного аргумента о чётности?

Вопросы к этой главе

Применима ли граница Хэмминга к нелинейному набору слов?

Да. В доказательстве нужны расстояние и число слов, а не генераторная матрица. Равенство M=2ᵏ относится только к линейному двоичному коду и добавляется после геометрического подсчёта.

Почему при d=4 гарантированный радиус всё ещё равен одному?

Два центра на расстоянии четыре могут иметь запись на расстоянии два от каждого. Для гарантированного однозначного исправления всех ошибок веса два нужно d≥5. Единственность ответа для какого-то одного принятого слова этого общего условия не меняет.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • SageMath: Hamming upper bound and Hamming-ball volume

    Сверены область применения, радиус и оценка мощности через объём шара. Пятисловное препятствие через чётность и проверенный четырёхсловный набор разобраны самостоятельно.

Две ошибки BCH: синдромы, локатор и поиск позиций

У принятого слова синдром третьей степени может оказаться нулём даже при двух ошибках. Поэтому одного теста «синдром равен нулю» недостаточно. Восстановим локатор из S₁ и S₃, переберём его корни в конечном поле и отдельно проверим исправленное слово. Все позиции ниже отсчитываются от степени x⁰.

Перед началом: Арифметика GF(2) и остатки многочленов; Операции в GF(16).

Почему синдром не содержит правильную часть сообщения

Двоичный примитивный BCH-код длины 15 с нулями α и α³; поле GF(16)=GF(2)[α]/(α⁴+α+1). Модель предполагает не более двух перевёрнутых битов.

Пусть α — корень неприводимого x⁴+x+1 и имеет порядок 15. Задан код, для которого c(α)=c(α³)=0. Полученное слово представляется r(x)=c(x)+e(x); сложение здесь означает XOR коэффициентов. Поэтому S₁=r(α)=e(α) и S₃=r(α³)=e(α³). Это не вещественные суммы: например, одинаковые слагаемые уничтожаются, а α⁴ заменяется на α+1.

При ошибках в разных позициях i,j обозначим X=αⁱ,Y=αʲ. Тогда S₁=X+Y и S₃=X³+Y³. Так как X≠Y, их сумма в характеристике два ненулевая. При одной ошибке S₁=X, а S₃=S₁³. Нулевая пара синдромов означает отсутствие ошибок только внутри принятой модели «не более двух»; больший ошибочный вектор может сам принадлежать коду.

От сумм степеней к локатору

Коэффициенты произведения (1+Xz)(1+Yz) равны σ₁=X+Y и σ₂=XY. Раскрывая (X+Y)³ в характеристике два, получаем S₁³=S₃+XY·S₁. Значит при S₁≠0 величина σ₂=(S₁³+S₃)/S₁ вычисляется делением в поле. Локатор Λ(z)=1+S₁z+σ₂z² не требует заранее угадывать обе позиции.

Его корни — X⁻¹ и Y⁻¹, а не X и Y. Чтобы проверить позицию k, вычисляют Λ(α⁻ᵏ); так устроен поиск Чена. Другая распространённая запись y²+S₁y+σ₂ имеет корни X,Y напрямую. Обе формы правильны, но смешивание их правил поиска заменяет ошибочные позиции другими. Нулевой σ₂ при ненулевом S₁ соответствует локатору степени один.

Какие проверки остаются после нахождения корней

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

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

Два переворота при нулевом S₃

Условие. В указанном поле принято r(x)=1+x²+x⁴+x⁶+x⁸. Известно, что передавалось слово кода с нулями α и α³, а перевёрнуто не больше двух битов. Найдите позиции и исправленное слово.

  1. Последовательное умножение на α с заменой α⁴=α+1 даёт S₁=r(α)=α¹² и S₃=r(α³)=0. Десятичная битовая запись S₁ в базисе 1,α,α²,α³ равна 15.
  2. В поле S₁³=α³⁶=α⁶, поэтому σ₂=α⁶/α¹²=α⁻⁶=α⁹. Получен локатор Λ(z)=1+α¹²z+α⁹z².
  3. Перебор k=0,…,14 находит Λ(α⁻ᵏ)=0 ровно при k=2 и k=7. Обратные корни равны α¹³ и α⁸; их нельзя читать как номера позиций напрямую.
  4. Переворот этих битов даёт c(x)=r(x)+x²+x⁷=1+x⁴+x⁶+x⁷+x⁸. В позиции 7 восстановлена единица, лишняя единица в позиции 2 удалена.
  5. Независимо c(x)=(x⁴+x+1)(x⁴+x³+x²+x+1). Оба требуемых нуля сохраняются; расстояние между r и c равно двум.

Ответ. Ошибки находятся в позициях 2 и 7. Исправленное слово: 1+x⁴+x⁶+x⁷+x⁸.

Проверка. Прямое вычисление синдромов всех 121 маски веса не больше двух находит единственную подходящую пару позиций. Значение S₃=0 не скрывает две ошибки: соответствующие кубы α⁶ и α²¹ совпадают и взаимно уничтожаются.

Где легко ошибиться. У Λ(z)=1+σ₁z+σ₂z² проверяются обратные степени α⁻ᵏ. Не заменяйте этот шаг поиском αᵏ и не объявляйте S₃=0 признаком отсутствия ошибок без проверки S₁ и модели канала.

Проверьте понимание

Какие позиции исправляются для разобранного r(x)=1+x²+x⁴+x⁶+x⁸ в GF(16) с α⁴=α+1?

Вопросы к этой главе

Что делать, если S₁=0, но S₃≠0?

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

Нужно ли при двоичном BCH отдельно определять величины ошибок?

Нет: ненулевая ошибка двоичного символа всегда означает переворот 0↔1. После установления позиций действие определено. В недвоичных кодах значения ошибок тоже неизвестны, и одного поиска позиций недостаточно.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • MIT 18.310: Correcting Errors in BCH Codes

    Прочитаны суммы первой и третьей степеней, связь с элементарными симметрическими функциями и проверка локатора по степеням. Собственный пример над GF(16) и все маски ошибок пересчитаны независимо; здесь используется обратная форма локатора Λ.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться