Забавный вопрос! На самом деле мы можем эффективно реализовать максимальное пространство сообщений размером $(q-1)^t({n\поверх t})$.
Начнем с случая $д=2$. Мы хотим сгенерировать битовую строку длины $n$ и вес Хэмминга точно $t$. Есть $C:=({n\поверх t})$ такие строки, и мы хотели бы отобразить целочисленное сообщение из интервала $[0,С-1]$ этому множеству биективно. Комбинаторно говоря, набор битовых строк соответствует комбинации (конкретно $t$-комбинации целых чисел от 0 до $n-1$). Мы можем биективно переписать нашу строку как строго убывающую последовательность $t$ ценности $n-1\ge c_t>c_{t-1}>\ldots>c_1\ge 0$ записывая индексы расположения единиц.
Теперь элегантная теорема математики, которую Кнут приписывает математику XIX века Эрнесто Паскалю, гласит, что каждое число $N$ может быть представлен в комбинаторная система счисления
$$N=\влево({c_t\поверх t}\справа)+\cdots+\влево({c_1\поверх 1}\справа)$$
и этот порядок шагов через комбинации является лексикографическим порядком (для наших целей первым $({n\поверх t})$ вес списка записей $t$ строки длины $n$). Следовательно, если у нас есть целое число $N\in [0,C-1]$ мы можем использовать жадный алгоритм для восстановления $N$й вес $t$ двоичная строка, заданная комбинаторной системой счисления. Вот некоторый псевдокод:
Инициализировать i:=n-1, j:=t, остаток=N
пока я>=0
если биномиальный (i, j) > остаток
установить бит i строки в 0
еще
установить бит i строки в 1
j--
остаток -= биномиальный (i, j)
я--
Обратная карта проста.
Например, с $n=10$, $т=3$ возможных комбинаций 120, найдем 17-ю (считая от 0 до). Сначала находим наименьшее тетраэдрическое число, не превышающее 17; Это $({5\поверх 3})=10$; мы отмечаем 5-е место и осталось 7. Теперь найдем наименьшее треугольное число, не большее 7; Это $({4\поверх 2})=6$; мы отмечаем 4-е место и остается 1. Теперь найдем наименьшее число, не большее 1; это $({1\поверх 1})=1$; мы отмечаем 1-е место и ничего не остается. Наша строка 0000110010. Если мы получаем строку, которую мы вычисляем $({5\поверх 3})+({4\поверх 2})+({1\поверх 1})=10+6+1=17$.
Для более общих алфавитов мы можем использовать описанный выше процесс, чтобы сгенерировать местоположения ошибок, а затем выбрать из $q-1$ возможные значения ошибок для каждого местоположения. Конкретно пусть $М=С(q-1)^t$ быть размером нашего пространства сообщения. Учитывая сообщение $m\in[0,M-1]$ мы позволяем $N=[м/(q-1)^t]$ так что $N\in[0,C-1]$ и создайте список местоположений, как указано выше. Затем мы позволим $B=m\mod{(q-1)^t}$ и писать $В$ как $t$-значное число в базе $(q-1)$ (допуская начальные нули) и присвойте каждому местоположению значения digit+1. Опять же, обратная карта проста.
Например, предположим, что у нас есть десятичный алфавит и мы рассматриваем строки длиной 10 с 3 ошибками. Возможных сообщений 120*729=87480; давайте найдем 12707-й. Мы нашли $N=[12707/729]=17$ и поэтому сгенерируйте ту же строку битов, что и выше. Мы нашли $B=12707\mod{729}=314$ что равно 378 по основанию 9. Наше сообщение преобразуется в строку с ошибкой 0000480090. Опять же, если мы получаем эту строку, мы вытаскиваем ненулевые цифры по порядку и вычитаем единицу из каждой, чтобы получить число 378 с основанием 9, так что $B=314$ точно так же мы знаем, что $N=17$ из мест ошибок и может вычислить $m=729N+B=12707$.
Глава 7.2.1.3 «Генерирование всех комбинаций» окончательной книги Дональда Кнута «Искусство компьютерного программирования» представляет собой превосходный исчерпывающий (хотя и отвлекающий) отчет о других алгоритмах для генерации комбинаций.
