Информатика / Кодирование информации
Граница Плоткина для двоичного кода большого расстояния
Когда минимальное расстояние двоичного кода превышает половину длины, попарные расстояния ограничивают число кодовых слов. Простой вариант границы Плоткина получается двойным подсчётом отличающихся битов.
Формула
При n=7 простой предел Плоткина равен8,3,2,2для d=4,5,6,7. Строгое условие d>3,5выполнено.
Обозначения
- $n$
- общая длина двоичных слов, бит
- $d$
- минимальное попарное расстояние, позиций
- $M$
- число кодовых слов, шт.
- $\lfloor x\rfloor$
- округление вниз до целого, —
Условия применения
Код состоит из M различных двоичных слов одной длины n, расстояние между каждой парой не меньше целого d. Обязательно строгое 2d>n. Линейность не требуется. Здесь используется простой вариант, полученный оценкой числа разногласий в каждом столбце сверху через M²/4.
Ограничения
При d=n/2 знаменатель обращается в нуль, и эту запись нельзя использовать. При меньшем расстоянии она не даёт полезной верхней границы. Для некоторых чётностей известны более точные варианты; приведённый предел остаётся необходимой оценкой и не доказывает существование кода с равенством.
Подробное объяснение
Сложим расстояния по всем неупорядоченным парам различных кодовых слов. Пар M(M−1)/2, каждая отличается минимум в d позициях, поэтому сумма не меньше M(M−1)d/2. Теперь тот же итог посчитаем по столбцам таблицы, в которой строки — кодовые слова.
Если в столбце w единиц и M−w нулей, он создаёт w(M−w) отличающихся пар. Квадратичное выражение максимально при равных долях и не превышает M²/4. По n столбцам суммарное расстояние не больше nM²/4. Сравнение нижнего и верхнего подсчётов даёт 2d(M−1)≤nM.
После переноса членов M(2d−n)≤2d. Разделить на 2d−n без изменения смысла верхней границы можно только при положительном знаменателе. Так возникает условие d>n/2. Поскольку M целое, дробь округляют вниз; округление вверх ослабило бы оценку и могло бы разрешить лишнее кодовое слово.
Смысл ограничения геометрический: множество слов не может одновременно иметь слишком много строк и слишком много разногласий в каждой паре. Баланс нулей и единиц в столбцах ограничивает общий запас отличий. В примерах с равенством обе стадии подсчёта должны быть точны: все расстояния одинаковы и столбцы сбалансированы.
Как пользоваться формулой
- Проверьте двоичный алфавит, общую длину n и минимальное расстояние d; вычислите знак 2d−n до деления.
- При 2d>nнайдите дробь 2d/(2d−n) и округлите её вниз для верхнего ограничения числа кодовых слов.
- Если дан конкретный код, независимо найдите все попарные расстояния и число единиц по столбцам для проверки предпосылок.
- Не переносите эту дробь на случай d=n/2; используйте соответствующую отдельную оценку или другую границу.
Историческая справка
Граница Плоткина входит в семейство геометрических и комбинаторных ограничений параметров исправляющих кодов. В отличие от доказательства через удаление координат или непересекающиеся шары она использует сумму всех попарных расстояний. Это выделяет область больших относительных расстояний, где высокая скорость передачи несовместима с сильным разделением слов.
В лекциях MIT по Essential Coding Theory за 2008 и 2013 годы граница рассматривается рядом с оценками Синглтона и Хэмминга. Современные учебные изложения используют разные варианты в зависимости от алфавита, чётности и режима расстояния. Приведённый двойной подсчёт сохраняет простую конечную форму для двоичного случая со строгим d>n/2; предельная асимптотическая запись требует отдельно следить за тем, как растут длина и размер кода.
Историческая линия формулы
Используется название «граница Плоткина» для стандартного ограничения кодов большого расстояния. Здесь явно указан простой двоичный вариант и область его применимости. Более сильные уточнения по чётности и обобщения на другие алфавиты не выдаются за ту же неизменную дробь.
Пример
Для двоичного кода длины 3 требуется расстояние хотя бы 2. Поскольку 2>3/2, применима граница. Она даёт M≤floor(4/(4−3))=4. Проверим, что в данном малом случае равенство достижимо. Возьмём слова 000,011,101,110. Любая пара различается ровно в двух позициях, всего 6 пар и суммарное расстояние 12. В каждом из трёх столбцов две единицы и два нуля, поэтому каждый даёт 2·2=4 отличающиеся пары; общий итог 3·4=12. Оба подсчёта совпали, код имеет 4 слова и достигает приведённой границы. Это явная конструкция именно для n=3,d=2; равенство в другом наборе параметров по одной формуле не гарантируется.
Частая ошибка
Нельзя применять дробь при неположительном знаменателе: отрицательный предел не имеет смысла размера кода. Суммируются неупорядоченные пары, поэтому множитель 1/2 нужен в нижнем подсчёте. Столбец с wединицами создаёт w(M−w), а не w²разногласий. Граница ограничивает число слов, а размерность линейного кода затем находят через M=2^k.
Практика
Задачи с решением
Семь битов
Условие. n=7,d=4. Ограничьте M.
Решение. 2d−n=8−7=1>0. M≤floor8/1=8.
Ответ. Не более 8 слов.
Шесть битов
Условие. n=6,d=4. Найдите предел числа слов.
Решение. 2d−n=2, поэтому M≤floor8/2=4. Для линейного двоичного кода это даёт k≤2.
Ответ. Не более 4 слов.
Дополнительные источники
- https://people.csail.mit.edu/madhu/ST13/scribe/lect04.pdf
- https://courses.csail.mit.edu/6.440/spring08/scribe/lec8.pdf
- https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/ada-coding-book.pdf
Связанные формулы
Информатика
Граница Синглтона: размер исправляющего кода
Граница Синглтона ограничивает число кодовых слов через длину блока, размер алфавита и минимальное расстояние. После удаления d−1 позиций разные кодовые слова должны оставаться различными.
Информатика
Граница Гилберта: существование разделённого кода
Жадное добавление слов строит код с расстоянием не меньше d. Когда добавить слово больше нельзя, шары радиуса d−1 покрывают всё пространство и дают нижнюю границу достижимого размера.
Информатика
Граница Грисмера: минимальная длина линейного кода
Граница Грисмера ограничивает длину линейного кода суммой округлённых расстояний. Она учитывает размерность и алфавит и часто сильнее простой оценки n≥k+d−1.
Информатика
Граница Хэмминга: сколько слов помещается в исправляющий код
Граница Хэмминга ограничивает число слов M двоичного блочного кода длины n, исправляющего любые t замен. Области возможных повреждений вокруг разных слов должны помещаться среди всех двоичных строк без пересечений.
Информатика
Расстояние Хэмминга между двоичными словами
Расстояние Хэмминга между двоичными словами: формула d(x,y)=\sum [x_i\ne y_i] помогает величины d, x_i, y_i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.