Двоичный симметричный канал

Двоичный симметричный канал (ДСК) — это простейшая модель канала передачи информации с помехами, в которой каждый передаваемый бит (0 или 1) может быть ошибочно принят как противоположный с фиксированной вероятностью \( p \), при этом вероятность правильной передачи равна \( 1-p \). ДСК является частным случаем дискретного канала без памяти и широко используется в теории информации и теории кодирования для анализа помехоустойчивости систем связи.

История

Модель двоичного симметричного канала была впервые формально описана Клодом Шенноном в его основополагающей работе «Математическая теория связи» (1948 год). Шеннон ввёл ДСК как абстракцию для изучения фундаментальных пределов передачи информации при наличии шума. До этого, в 1920-х годах, Гарри Найквист и Ральф Хартли исследовали влияние помех на телеграфные линии, но именно Шеннон предложил вероятностную модель, ставшую стандартом. В последующие десятилетия ДСК оставался ключевым инструментом для разработки кодов, исправляющих ошибки, таких как коды Хэмминга (1950 год) и свёрточные коды.

Определение и параметры

ДСК представляет собой дискретный канал с входным алфавитом \( X = \{0, 1\} \), выходным алфавитом \( Y = \{0, 1\} \) и матрицей переходных вероятностей:

\[ P(Y = y | X = x) = \begin{cases} 1-p, & \text{если } y = x, \\ p, & \text{если } y \neq x. \end{cases} \]

Здесь \( p \) — вероятность ошибки (симметричная для обоих битов), \( 0 \leq p \leq 1 \). Канал считается симметричным, так как вероятности ошибок для 0 и 1 одинаковы. Если \( p = 0 \), канал является идеальным (безошибочным); если \( p = 0,5 \), выходная последовательность не зависит от входной (канал становится бесполезным). В реальных системах \( p \) обычно мало (например, \( 10^{-3} \) или \( 10^{-6} \)).

Пропускная способность

Пропускная способность ДСК — максимальная скорость передачи информации (в битах на использование канала), при которой возможна передача с произвольно малой вероятностью ошибки. Для ДСК она вычисляется по формуле:

\[ C = 1 - H(p) = 1 - [ -p \log_2 p - (1-p) \log_2 (1-p) ], \]

где \( H(p) \) — бинарная энтропийная функция. При \( p = 0 \) \( C = 1 \) бит/использование; при \( p = 0,5 \) \( C = 0 \). Например, для \( p = 0,1 \) пропускная способность составляет примерно 0,531 бит/использование. Это означает, что при кодировании можно достичь скорости до 0,531 бита на передачу, обеспечив надёжность.

Применение в теории кодирования

ДСК служит базовой моделью для тестирования и сравнения кодов, исправляющих ошибки. Основные типы кодов, применяемых для ДСК:

• Блочные коды (например, коды Хэмминга, БЧХ, Рида — Соломона): разбивают данные на блоки фиксированной длины и добавляют избыточные биты для обнаружения и исправления ошибок.
• Свёрточные коды: работают с непрерывным потоком данных, используя память для кодирования.
• Турбо-коды и LDPC-коды (коды с малой плотностью проверок на чётность): приближаются к пропускной способности ДСК при больших длинах блоков.

Вероятность ошибки после декодирования зависит от \( p \), длины кода и алгоритма декодирования. Например, для кода Хэмминга (7,4) вероятность ошибки на бит после декодирования при \( p = 0,01 \) составляет около \( 10^{-4} \).

Ограничения и критика

ДСК является упрощённой моделью, не учитывающей ряд особенностей реальных каналов:

• Память канала: в реальных системах (например, в радиоканалах с замираниями) ошибки часто группируются (пакеты ошибок), а не распределяются независимо. ДСК предполагает отсутствие памяти, что не всегда верно.
• Несимметричность: в некоторых каналах (например, оптических) вероятность ошибки для 0 и 1 может различаться, что требует модели асимметричного канала.
• Многопозиционные сигналы: ДСК применим только к двоичной передаче; для более сложных модуляций (QAM, PSK) используются модели с большими алфавитами.

Несмотря на эти ограничения, ДСК остаётся полезным для теоретического анализа и начального проектирования систем связи.

Примеры использования

• Спутниковая связь: ДСК применяется для оценки эффективности кодов в каналах с аддитивным белым гауссовским шумом (АБГШ) после квантования сигнала.
• Цифровое телевидение: стандарты DVB-T и DVB-S используют коды, рассчитанные на модель ДСК с заданной вероятностью ошибки.
• Хранение данных: в жёстких дисках и флеш-памяти модель ДСК используется для анализа кодов коррекции ошибок (например, кодов Рида — Соломона).

Связанные модели

• Двоичный стирающий канал (ДСК-стирание): вместо ошибки бит может быть стёрт (обозначен как «?»), что упрощает кодирование.
• Канал с аддитивным белым гауссовским шумом (АБГШ): более реалистичная модель для аналоговых сигналов, которая может быть сведена к ДСК после квантования.
• Канал с памятью (например, канал Гилберта — Эллиота): учитывает пакетирование ошибок.

Интересные факты

• Теорема Шеннона о кодировании для ДСК гарантирует существование кодов, достигающих пропускной способности, но не указывает способ их построения. Практические коды, близкие к пределу, были найдены лишь в 1990-х годах (турбо-коды).
• ДСК является частным случаем более общего класса — симметричных каналов, где все строки матрицы переходных вероятностей являются перестановками друг друга.
• Вероятность ошибки \( p \) в ДСК часто интерпретируется как отношение сигнал/шум (SNR) в логарифмической шкале.

Источники

• Шеннон К. Математическая теория связи. — 1948.
• Мак-Элис Р. Теория информации и кодирование. — Мир, 1976.
• Галлагер Р. Теория информации и надёжная связь. — Советское радио, 1974.
• Прокис Дж. Цифровая связь. — Радио и связь, 2000.