Введение
Бинарный симметричный канал (или BSCp) — это распространенная модель коммуникационного канала, используемая в теории кодирования и теории информации. В этой модели передатчик стремится отправить бит (0 или 1), а приемник получает бит. Бит с вероятностью p подвергается инверсии ("переворачивается"), в противном случае он принимается верно. Эта модель может быть применена к различным каналам связи, таким как телефонные линии или хранилища данных на дисках. К BSCp применима теорема о кодировании с помехами, утверждающая, что информацию можно передавать с любой скоростью вплоть до емкости канала с произвольно малой вероятностью ошибки. Емкость канала составляет битов, где — бинарная энтропия. Для эффективной передачи информации по каналу были разработаны коды, включая код Форни.
Определение
Бинарный симметричный канал с вероятностью переключения, обозначаемый BSCp, — это канал с бинарным входом и бинарным выходом, вероятность ошибки в котором равна p. То есть, если X — передаваемая случайная величина, а Y — принятая величина, то канал характеризуется условными вероятностями:
Предполагается, что если p < 0.5, то приемник может инвертировать выходной сигнал (воспринимать 1 при получении 0 и наоборот) и получить эквивалентный канал с вероятностью переключения 1-p.
Теорема кодирования шумовых каналов
Теорема Шеннона об кодировании с помехами дает результат о скорости передачи информации по каналу связи с произвольно малой вероятностью ошибки. Мы рассматриваем частный случай, когда шум, характеризующий канал, является случайной величиной, состоящей из n независимых случайных битов (n определено ниже), где каждый случайный бит равен 0 с вероятностью p и 1 с вероятностью 1-p. Мы обозначаем это как "B(n, p)". Эта теорема фактически подразумевает, что если сообщение выбрано из некоторого множества M, закодировано случайной кодирующей функцией и передано по зашумленному каналу, то существует очень высокая вероятность восстановления исходного сообщения при декодировании, если скорость передачи информации меньше или равна величине, указанной в теореме. Вероятность ошибки декодирования экспоненциально мала.
The noise that characterizes is a random variable consisting of n independent random bits (n is defined below) where each random bit is a with probability and a with probability We indicate this by writing "". What this theorem actually implies is, a message when picked from , encoded with a random encoding function , and sent across a noisy , there is a very high probability of recovering the original message by decoding, if or in effect the rate of the channel is bounded by the quantity stated in the theorem. The decoding error probability is exponentially small.
Конверс теоремы пропускной способности Шеннона
Обратная теорема о пропускной способности, по сути, утверждает, что является наилучшей скоростью, которой можно достичь по бинарному симметричному каналу. Формально теорема гласит:
Интуиция, лежащая в основе доказательства, заключается в том, что число ошибок быстро растет при увеличении скорости передачи сверх пропускной способности канала. Идея состоит в том, что отправитель генерирует сообщения размерности , в то время как канал вносит ошибки при передаче. Когда пропускная способность канала равна , число ошибок обычно составляет для кода блочной длины . Максимальное число сообщений равно . Выход канала, с другой стороны, имеет возможных значений. Если возникает путаница между какими-либо двумя сообщениями, то, вероятно, мы получим , что является нежелательным случаем, поскольку мы хотим, чтобы вероятность ошибки декодирования оставалась экспоненциально малой.
Коды
Совсем недавно было проделано и продолжается много работы по разработке явных кодов коррекции ошибок для достижения пропускной способности нескольких стандартных каналов связи. Мотивация разработки таких кодов заключается в установлении связи между скоростью кода и долей ошибок, которые он способен исправлять. При разработке кодов, достигающих пропускной способности каналов или канала бинарного стирания, применяется подход, заключающийся в исправлении меньшего числа ошибок с высокой вероятностью и достижении максимально возможной скорости. Теорема Шеннона определяет наилучшую скорость, которую можно достичь через канал, но не предоставляет информации о конкретных кодах, достигающих этой скорости. Фактически, такие коды обычно строятся для исправления лишь небольшой доли ошибок с высокой вероятностью, но при этом обеспечивают очень хорошую скорость. Первый такой код был разработан Джорджем Д. Форни в 1966 году. Этот код является каскадным, построенным путем объединения двух различных типов кодов.
Кодекс Форни
Форни построил каскадный код для достижения пропускной способности, установленной теоремой кодирования с шумом для В его коде внешний код представляет собой код блочной длины и скорости над полем , и, кроме того, существует алгоритм декодирования для , способный исправлять до доли ошибок в наихудшем случае и работающий за время . Внутренний код – это код блочной длины, размерности и скорости. Кроме того, для него существует алгоритм декодирования с вероятностью ошибки декодирования не более чем за и временем работы . Для внешнего кода первым, что приходит на ум, был бы код Рида-Соломона. Однако мы увидим, что построение такого кода невозможно за полиномиальное время. Именно поэтому для используется двоичный линейный код. Для внутреннего кода мы находим линейный код путем полного перебора из линейного кода блочной длины и размерности, скорость которого соответствует пропускной способности, установленной теоремой кодирования с шумом. Эта скорость почти достигает пропускной способности. Отметим также, что кодирование и декодирование можно выполнить за полиномиальное время относительно . Фактически, кодирование занимает время . Более того, описанный алгоритм декодирования занимает время, при условии, что ; и .
The outer code is a code of block length and rate over the field , and Additionally, we have a decoding algorithm for which can correct up to fraction of worst case errors and runs in time. The inner code is a code of block length , dimension , and a rate of Additionally, we have a decoding algorithm for with a decoding error probability of at most over and runs in time. For the outer code , a Reed Solomon code would have been the first code to have come in mind. However, we would see that the construction of such a code cannot be done in polynomial time. This is why a binary linear code is used for
For the inner code we find a linear code by exhaustively searching from the linear code of block length and dimension , whose rate meets the capacity of , by the noisy channel coding theorem. The rate which almost meets the capacity. We further note that the encoding and decoding of can be done in polynomial time with respect to As a matter of fact, encoding takes time Further, the decoding algorithm described takes time as long as ; and .
Приложения
Бинарный симметричный канал может моделировать жесткий диск, используемый для хранения данных: вход канала представляет собой бит, записываемый на диск, а выход – бит, считываемый позднее. Ошибки могут возникать из-за изменения намагниченности, фонового шума или сбоя в работе записывающей головки. Другие объекты, которые можно смоделировать с помощью бинарного симметричного канала, включают телефонную или радиосвязь, а также деление клеток, при котором дочерние клетки получают информацию ДНК от родительской клетки. Этот канал часто используется теоретиками, поскольку он является одним из самых простых зашумленных каналов для анализа. Многие задачи теории связи могут быть сведены к BSC. И наоборот, возможность эффективной передачи данных по BSC может привести к решениям для более сложных каналов.