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

1) Энтропия источника

Энтропия H(X) измеряет среднее количество информации (в битах) в одном символе случайного источника X:
H(X) = − sum_x P(X=x) log2 P(X=x).Для двоичного источника с вероятностью единицы q (Бернулли(q)):
H2(q) = − q log2 q − (1−q) log2(1−q) (бинарная энтропия).Если источник равномерный (q = 1/2), H2(1/2) = 1 бит/символ — максимум.

2) Пропускная способность (ёмкость) канала

Ёмкость канала C — максимальное число бит информации, которые можно передать через канал в среднем за один каналный символ с произвольно малой вероятностью ошибки (при неограниченно большом блоке).Для двоичного симметричного канала (BSC) с вероятностью ошибки p (кроссовера) ёмкость:
C = 1 − H2(p) (бит/кан.использование),
где H2(p) — бинарная энтропия ошибки.Более общая формула: C = max_{P_X} I(X;Y) (максимум взаимной информации по распределению входа).

3) Условие возможности передачи «без ошибок»

В теореме Шеннона «без ошибок» понимается: можно сделать вероятность ошибки сколь угодно малой (не обязательно нулевая) при больших блоках.Если вы кодируете k информационных бит в n каналных символов, скорость R = k/n (бит/кан.использование). Теорема Шеннона: если R < C, то существуют коды с длиной n→∞, дающие вероятность ошибки → 0. Если R > C — ошибка не может быть сделана мала.Для конечной длины n существуют ограничения конечной длины (finite-blocklength) — нельзя гарантировать сколь угодно малую ошибку, и нужны конкретные оценки для n, p и требуемого уровня ошибки.

4) Строго нулевая вероятность ошибки

Если p>0 (канал «шумный»), то строгой гарантии нулевой вероятности ошибок для всех сообщений обычно нет (нулевая-error ёмкость большинства шумных каналов равна 0, если выходы разных входов перекрываются по поддержке). Практически работает асимптотическая гарантия Шеннона (вероятность ошибки стремится к 0 при n→∞, если R<C).

5) Практические критерии для конечного n

Если вы хотите гарантировать коррекцию до t ошибок в блоке длины n (т.е. «без ошибок» против всех паттернов ≤t), код должен иметь минимальное расстояние d ≥ 2t+1.Hamming bound (sphere-packing): M · sum_{i=0}^t C(n,i) ≤ 2^n, где M = 2^k — число кодовых слов, k = число информационных бит. Это даёт верхнюю границу на достижимые параметры (n,k,d).Для практики: оцените вероятность того, что число ошибок > t:
P{>t ошибок} = sum_{i=t+1}^{n} C(n,i) p^i (1−p)^{n−i}.
Требуем, чтобы эта вероятность была < ваш целевой уровень ошибок.

6) Пример практического кодека для малого N

A) Hamming-код (классический для небольших блоков, исправляет одну ошибку)

Параметры: Hamming(n=2^r−1, k=2^r−r−1), исправляет 1 ошибку (d_min = 3).Пример Hamming(7,4): кодирует 4 информационных бита в 7 бит; скорость R = 4/7 ≈ 0.571.
Расположение: позиции 1,2,4 — контрольные биты (чётности), позиции 3,5,6,7 — данные.
Контрольные биты вычисляются как XOR нескольких данных:
p1 = b3 ⊕ b5 ⊕ b7
p2 = b3 ⊕ b6 ⊕ b7
p3 = b5 ⊕ b6 ⊕ b7
Декодирование: приёмуем слово r, считаем синдром s = H · r^T (вектор 3 бита) — он равен двоичному представлению номера ошибочного бита; если s≠0, инвертируем бит на позиции s.Применимость: хорошо работает при малых p и когда достаточно исправлять только одиночные ошибки; при более высоких p остаточная частота не исправляемых ошибок (двух и более) может быть велика.

B) Свёрточный код (для потоковой передачи, хорошо для коротких/средних задержек)

Пример: частота 1/2, constraint length K=3, генераторы g1=111(=7), g2=101(=5) (в двоичном/восьмеричном представлении).
Код выдаёт по 2 бита на каждый входный бит. Скорость R = 1/2.Кодирование: входные биты идут через сдвиговый регистр длины K; выходы — XOR выбранных регистров по генераторным многочленам.Декодирование: Viterbi-алгоритм (максимум правдоподобия по траектории); при небольших блоках и умеренной вычислительной сложности даёт отличную производительность.Для конечных сообщений необходимо «завершить» регистр (K−1 нулей) или использовать терминированный/не терминированный вариант.

7) Как подобрать код при заданных N, p и требуемой ошибке ε

Выберите желаемую скорость R = N/n, учитывая, что нужно R < C для возможности малой ошибки при больших n.Для фиксированного n оцените вероятностную производительность: выберите код с минимальным расстоянием d, такое что P{>t = floor((d−1)/2) ошибок} < ε (используя биномиальное распределение).Для очень малых N часто применяют Hamming, BCH (корректируют также несколько ошибок) или свёрточные коды с Viterbi, в зависимости от требуемой пропускной способности и задержки.

8) Краткие рекомендации

Если p невелик (например <0.05) и N мало: Hamming(7,4) или BCH(15,11) могут быть простыми и эффективными.Если нужны лучшая коррекция при умеренном размере блока: BCH или короткие рида–соломон (если канал с ошибками блоков) либо свёрточный код (с Viterbi) при потоковых данных.Если требуется теоретически минимальная вероятность ошибки и доступен большой блок n: выбирайте код с R<C и используйте современные коды (LDPC, Turbo) — они приближаются к ёмкости.

Если хотите, могу:

Привести конкретный расчёт: для заданных N, p и допустимого уровня ошибок ε подобрать n и предложить конкретный код (Hamming/BCH/свёрточный) и оценить вероятность ошибок;Показать шаг за шагом кодирование/декодирование Hamming(7,4) на конкретном примере.