Бинарный симметричный канал

Бинарный симметричный канал (или BSC _p ) — это распространенная модель канала связи, используемая в теории кодирования и теории информации . В этой модели передатчик хочет отправить бит (ноль или единицу), а получатель получит бит. Бит будет «перевернут» с « вероятностью пересечения » p , ​​а в противном случае будет принят правильно. Эту модель можно применять к различным каналам связи, таким как телефонные линии или дисковые накопители.

применима теорема кодирования шумного канала К BSC _p , утверждающая, что информация может передаваться на любой скорости, вплоть до пропускной способности канала, со сколь угодно малой ошибкой. Пропускная способность канала $1-\operatorname {H} _{\text{b}}(p)$ биты, где $\operatorname {H} _{\text{b}}$ — двоичная функция энтропии . Коды, включая код Форни, были разработаны для эффективной передачи информации по каналу.

Определение

Двоичный симметричный канал воспринимает каждый бит сообщения, переданного правильно с вероятностью 1– p и неправильно с вероятностью p из-за шума в среде передачи.

Двоичный симметричный канал с вероятностью пересечения $p$, обозначенный BSC _p , представляет собой канал с двоичным входом и двоичным выходом и вероятностью ошибки. $p$. То есть, если $X$ – передаваемая случайная величина и $Y$ полученной переменной, то канал характеризуется условными вероятностями :

${\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1-p\\\operatorname {Pr} [Y=0|X=1]&=p\\\operatorname {Pr} [Y=1|X=0]&=p\\\operatorname {Pr} [Y=1|X=1]&=1-p\end{aligned}}$

Предполагается, что $0\leq p\leq 1/2$. Если $p>1/2$, то приемник может поменять выходной сигнал (интерпретировать 1, когда он видит 0, и наоборот) и получить эквивалентный канал с вероятностью пересечения $1-p\leq 1/2$.

Вместимость

График, показывающий долю пропускной способности канала ( ось Y ), которая может быть использована для полезной нагрузки, в зависимости от уровня шума канала (вероятность переворота битов; ось X ).

Пропускная способность двоичного симметричного канала в битах равна:

$\ C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p),$

где $\operatorname {H} _{\text{b}}(p)$ — двоичная функция энтропии , определяемая следующим образом:

$\operatorname {H} _{\text{b}}(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}$

showДоказательство

The capacity is defined as the maximum mutual information between input and output for all possible input distributions $p_{X}(x)$: $C=\max _{p_{X}(x)}\left\{\,I(X;Y)\,\right\}$ The mutual information can be reformulated as ${\begin{aligned}I(X;Y)&=H(Y)-H(Y|X)\\&=H(Y)-\sum _{x\in \{0,1\}}{p_{X}(x)H(Y|X=x)}\\&=H(Y)-\sum _{x\in \{0,1\}}{p_{X}(x)}\operatorname {H} _{\text{b}}(p)\\&=H(Y)-\operatorname {H} _{\text{b}}(p),\end{aligned}}$ where the first and second step follows from the definition of mutual information and conditional entropy respectively. The entropy at the output for a given and fixed input symbol ($H(Y|X=x)$) equals the binary entropy function, which leads to the third line and this can be further simplified. In the last line, only the first term $H(Y)$ depends on the input distribution $p_{X}(x)$. The entropy of a binary variable is at most 1 bit, and equality is attained if its probability distribution is uniform. It therefore suffices to exhibit an input distribution that yields a uniform probability distribution for the output $Y$. For this, note that it is a property of any binary symmetric channel that a uniform probability distribution of the input results in a uniform probability distribution of the output. Hence the value $H(Y)$ will be 1 when we choose a uniform distribution for $p_{X}(x)$. We conclude that the channel capacity for our binary symmetric channel is $C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p)$.

каналом

Теорема Шеннона о кодировании шумного канала дает результат о скорости передачи информации по каналу связи со сколь угодно малой ошибкой. Мы изучаем частный случай ${\text{BSC}}_{p}$.

Шум $e$ это характеризует ${\text{BSC}}_{p}$ — случайная величина, состоящая из n независимых случайных битов (n определено ниже), где каждый случайный бит представляет собой $1$ с вероятностью $p$ и $0$ с вероятностью $1-p$. Мы обозначаем это, написав « $e\in {\text{BSC}}_{p}$".

Теорема — Для всех $p<{\tfrac {1}{2}},$ все $0<\epsilon <{\tfrac {1}{2}}-p$, все достаточно большие $n$ (в зависимости от $p$ и $\epsilon$), и все $k\leq \lfloor (1-H(p+\epsilon ))n\rfloor$, существует пара функций кодирования и декодирования $E:\{0,1\}^{k}\to \{0,1\}^{n}$ и $D:\{0,1\}^{n}\to \{0,1\}^{k}$ соответственно, так что каждое сообщение $m\in \{0,1\}^{k}$ имеет следующее свойство:

$\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\leq 2^{-{\delta }n}$.

На самом деле из этой теоремы следует, что сообщение, выбранное из $\{0,1\}^{k}$, закодированный с помощью функции случайного кодирования $E$и отправили через шумный ${\text{BSC}}_{p}$, существует очень высокая вероятность восстановления исходного сообщения путем декодирования, если $k$ или, по сути, скорость канала ограничена величиной, указанной в теореме. Вероятность ошибки декодирования экспоненциально мала.

Доказательство

Теорему можно доказать непосредственно вероятностным методом . Рассмотрим функцию кодирования $E:\{0,1\}^{k}\to \{0,1\}^{n}$ который выбирается случайно. Это означает, что для каждого сообщения $m\in \{0,1\}^{k}$, значение $E(m)\in \{0,1\}^{n}$ выбирается случайным образом (с равными вероятностями). Для данной функции кодирования $E$, функция декодирования $D:\{0,1\}^{n}\to \{0,1\}^{k}$ указывается следующим образом: учитывая любое полученное кодовое слово $y\in \{0,1\}^{n}$, мы находим сообщение $m\in \{0,1\}^{k}$ такое, что расстояние Хэмминга $\Delta (y,E(m))$ как можно меньше (с произвольным разрывом связей). ( $D$ называется функцией декодирования максимального правдоподобия .)

Доказательство продолжается, показывая, что по крайней мере один такой выбор $(E,D)$ удовлетворяет заключению теоремы путем интегрирования по вероятностям. Предполагать $p$ и $\epsilon$ фиксированы. Сначала покажем, что для фиксированного $m\in \{0,1\}^{k}$ и $E$ выбрано случайно, вероятность неудачи в течение ${\text{BSC}}_{p}$ шум экспоненциально мал по n . На этом этапе доказательство работает для фиксированного сообщения. $m$. Далее мы расширим этот результат, чтобы он работал для всех сообщений. $m$. Мы достигаем этого, исключая половину кодовых слов из кода, аргументируя это тем, что доказательство вероятности ошибки декодирования справедливо по крайней мере для половины кодовых слов. Последний метод называется очисткой. Это дает всему процессу название «случайное кодирование с удалением» .

showПродолжение доказательства (набросок)

Fix $p$ and $\epsilon$. Given a fixed message $m\in \{0,1\}^{k}$, we need to estimate the expected value of the probability of the received codeword along with the noise does not give back $m$ on decoding. That is to say, we need to estimate: $\mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\right].$ Let $y$ be the received codeword. In order for the decoded codeword $D(y)$ not to be equal to the message $m$, one of the following events must occur: $y$ does not lie within the Hamming ball of radius $(p+\epsilon )n$ centered at $E(m)$. This condition is mainly used to make the calculations easier. There is another message $m'\in \{0,1\}^{k}$ such that $\Delta (y,E(m'))\leqslant \Delta (y,E(m))$. In other words, the errors due to noise take the transmitted codeword closer to another encoded message. We can apply the Chernoff bound to ensure the non occurrence of the first event; we get: $Pr_{e\in {\text{BSC}}_{p}}[\Delta (y,E(m))>(p+\epsilon )n]\leqslant 2^{-{\epsilon ^{2}}n}.$ This is exponentially small for large $n$ (recall that $\epsilon$ is fixed). For the second event, we note that the probability that $E(m')\in B(y,(p+\epsilon )n)$ is ${\text{Vol}}(B(y,(p+\epsilon )n)/2^{n}$ where $B(x,r)$ is the Hamming ball of radius $r$ centered at vector $x$ and ${\text{Vol}}(B(x,r))$ is its volume. Using approximation to estimate the number of codewords in the Hamming ball, we have ${\text{Vol}}(B(y,(p+\epsilon )n))\approx 2^{H(p)n}$. Hence the above probability amounts to $2^{H(p)n}/2^{n}=2^{H(p)n-n}$. Now using the union bound, we can upper bound the existence of such an $m'\in \{0,1\}^{k}$ by $\leq 2^{k+H(p)n-n}$ which is $2^{-\Omega (n)}$, as desired by the choice of $k$.

showПродолжение доказательства (подробное)

From the above analysis, we calculate the probability of the event that the decoded codeword plus the channel noise is not the same as the original message sent. We shall introduce some symbols here. Let $p(y|E(m))$ denote the probability of receiving codeword $y$ given that codeword $E(m)$ was sent. Let $B_{0}$ denote $B(E(m),(p+\epsilon )n).$ ${\begin{aligned}\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]&=\sum _{y\in \{0,1\}^{n}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant \sum _{y\notin B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}+\sum _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\end{aligned}}$ We get the last inequality by our analysis using the Chernoff bound above. Now taking expectation on both sides we have, ${\begin{aligned}\mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\right]&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}p(y|E(m))\mathbb {E} [1_{D(y)\neq m}]\\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}\mathbb {E} [1_{D(y)\neq m}]&&\sum _{y\in B_{0}}p(y|E(m))\leqslant 1\\&\leqslant 2^{-{\epsilon ^{2}}n}+2^{k+H(p+\epsilon )n-n}&&\mathbb {E} [1_{D(y)\neq m}]\leqslant 2^{k+H(p+\epsilon )n-n}{\text{ (see above)}}\\&\leqslant 2^{-\delta n}\end{aligned}}$ by appropriately choosing the value of $\delta$. Since the above bound holds for each message, we have $\mathbb {E} _{m}\left[\mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D(E(m)+e)\right]\neq m\right]\right]\leqslant 2^{-\delta n}.$ Now we can change the order of summation in the expectation with respect to the message and the choice of the encoding function $E$. Hence: $\mathbb {E} _{E}\left[\mathbb {E} _{m}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D(E(m)+e)\right]\neq m\right]\right]\leqslant 2^{-\delta n}.$ Hence in conclusion, by probabilistic method, we have some encoding function $E^{*}$ and a corresponding decoding function $D^{*}$ such that $\mathbb {E} _{m}\left[\Pr _{e\in {\text{BSC}}_{p}}\left[D^{*}(E^{*}(m)+e)\neq m\right]\right]\leqslant 2^{-\delta n}.$ At this point, the proof works for a fixed message $m$. But we need to make sure that the above bound holds for all the messages $m$ simultaneously. For that, let us sort the $2^{k}$ messages by their decoding error probabilities. Now by applying Markov's inequality, we can show the decoding error probability for the first $2^{k-1}$ messages to be at most $2\cdot 2^{-\delta n}$. Thus in order to confirm that the above bound to hold for every message $m$, we could just trim off the last $2^{k-1}$ messages from the sorted order. This essentially gives us another encoding function $E'$ with a corresponding decoding function $D'$ with a decoding error probability of at most $2^{-\delta n+1}$ with the same rate. Taking $\delta '$ to be equal to $\delta -{\tfrac {1}{n}}$ we bound the decoding error probability to $2^{-\delta 'n}$. This expurgation process completes the proof.

Шеннона о

Обратная теорема о емкости по существу утверждает, что $1-H(p)$ — это лучшая скорость, которую можно достичь по двоичному симметричному каналу. Формально теорема гласит:

Теорема — Если $k$ $\geq$ $\lceil$ $(1-H(p+\epsilon )n)$ $\rceil$ тогда следующее верно для каждой кодирования и декодирования функции $E$: $\{0,1\}^{k}$ $\rightarrow$ $\{0,1\}^{n}$ и $D$: $\{0,1\}^{n}$ $\rightarrow$ $\{0,1\}^{k}$ соответственно: $\Pr _{e\in {\text{BSC}}_{p}}$[ $D(E(m)+e)$ $\neq$ $m]$ $\geq$ ${\frac {1}{2}}$.

Однако интуиция, лежащая в основе доказательства, показывает, что количество ошибок быстро растет по мере того, как скорость выходит за пределы пропускной способности канала. Идея заключается в том, что отправитель генерирует сообщения размером $k$, в то время как канал ${\text{BSC}}_{p}$ вносит ошибки передачи. Когда пропускная способность канала $H(p)$, количество ошибок обычно $2^{H(p+\epsilon )n}$ для кода длиной блока $n$. Максимальное количество сообщений $2^{k}$. Выход канала, с другой стороны, имеет $2^{n}$ возможные значения. Если между любыми двумя сообщениями есть какая-либо путаница, вполне вероятно, что $2^{k}2^{H(p+\epsilon )n}\geq 2^{n}$. Следовательно, мы имели бы $k\geq \lceil (1-H(p+\epsilon )n)\rceil$, случая, которого нам хотелось бы избежать, чтобы вероятность ошибки декодирования была экспоненциально малой.

Коды

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

Подход к разработке кодов, соответствующих пропускной способности каналов ${\text{BSC}}$ или канал двоичного стирания ${\text{BEC}}$ Целью было исправить меньшее количество ошибок с высокой вероятностью и достичь максимально возможной скорости. Теорема Шеннона дает нам наилучшую скорость, которую можно достичь за ${\text{BSC}}_{p}$, но это не дает нам представления о каких-либо явных кодах, которые достигают такой скорости. Фактически такие коды обычно создаются для исправления лишь небольшой части ошибок с высокой вероятностью, но при этом достигают очень хорошей скорости. Первый такой код был создан Джорджем Д. Форни в 1966 году. Этот код представляет собой составной код, образованный путем объединения двух разных типов кодов.

Код Форни

Форни построил составной код. $C^{*}=C_{\text{out}}\circ C_{\text{in}}$ для достижения пропускной способности теоремы кодирования шумного канала для ${\text{BSC}}_{p}$. В его коде

• Внешний код $C_{\text{out}}$ это код длины блока $N$ и оцените $1-{\frac {\epsilon }{2}}$ над полем $F_{2^{k}}$, и $k=O(\log N)$. Кроме того, у нас есть декодирования алгоритм $D_{\text{out}}$ для $C_{\text{out}}$ который может исправить до $\gamma$ доля ошибок в худшем случае и выполняется в $t_{\text{out}}(N)$ время.
• Внутренний код $C_{\text{in}}$ это код длины блока $n$, измерение $k$, и скорость $1-H(p)-{\frac {\epsilon }{2}}$. Кроме того, у нас есть алгоритм декодирования $D_{\text{in}}$ для $C_{\text{in}}$ с вероятностью ошибки декодирования не более ${\frac {\gamma }{2}}$ над ${\text{BSC}}_{p}$ и вбегает $t_{\text{in}}(N)$ время.

Для внешнего кода $C_{\text{out}}$, код Рида-Соломона был первым кодом, который пришел на ум. Однако мы увидим, что построение такого кода не может быть выполнено за полиномиальное время. Вот почему двоичный линейный код используется для $C_{\text{out}}$.

Для внутреннего кода $C_{\text{in}}$ мы находим линейный код путем исчерпывающего поиска по линейному коду длины блока $n$ и размер $k$, скорость которого соответствует мощности ${\text{BSC}}_{p}$, по теореме кодирования канала с шумом.

Ставка $R(C^{*})=R(C_{\text{in}})\times R(C_{\text{out}})=(1-{\frac {\epsilon }{2}})(1-H(p)-{\frac {\epsilon }{2}})\geq 1-H(p)-\epsilon$ что почти соответствует ${\text{BSC}}_{p}$ емкость. Далее отметим, что кодирование и декодирование $C^{*}$ можно сделать за полиномиальное время относительно $N$. По сути, кодировка $C^{*}$ требует времени $O(N^{2})+O(Nk^{2})=O(N^{2})$. Кроме того, описанный алгоритм декодирования требует времени $Nt_{\text{in}}(k)+t_{\text{out}}(N)=N^{O(1)}$ пока $t_{\text{out}}(N)=N^{O(1)}$; и $t_{\text{in}}(k)=2^{O(k)}$.

ошибки

Естественный алгоритм декодирования $C^{*}$ это:

• Предполагать $y_{i}^{\prime }=D_{\text{in}}(y_{i}),\quad i\in (0,N)$
• Выполнять $D_{\text{out}}$ на $y^{\prime }=(y_{1}^{\prime }\ldots y_{N}^{\prime })$

Обратите внимание, что каждый блок кода для $C_{\text{in}}$ считается символом $C_{\text{out}}$. Теперь, поскольку вероятность ошибки по любому индексу $i$ для $D_{\text{in}}$ самое большее ${\tfrac {\gamma }{2}}$ и ошибки в ${\text{BSC}}_{p}$ независимы, ожидаемое количество ошибок для $D_{\text{in}}$ самое большее ${\tfrac {\gamma N}{2}}$ по линейности ожидания. Теперь, применяя оценку Чернова , мы имеем ограниченную вероятность ошибки более чем $\gamma N$ возникающие ошибки $e^{\frac {-\gamma N}{6}}$. Поскольку внешний код $C_{\text{out}}$ максимум могу исправить $\gamma N$ ошибок, это декодирования вероятность ошибки $C^{*}$. Если это выразить в асимптотических терминах, это дает нам вероятность ошибки $2^{-\Omega (\gamma N)}$. Таким образом, достигнутая вероятность ошибки декодирования $C^{*}$ экспоненциально мало, как и теорема о кодировании канала с шумом.

Мы дали общую методику построения $C^{*}$. Более подробные описания на $C_{\text{in}}$ и $C_{\text{out}}$ пожалуйста, прочитайте следующие ссылки. Недавно было также разработано несколько других кодов для достижения этих возможностей. LDPC из-за их более быстрого времени декодирования. Для этой цели были рассмотрены коды

Приложения

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

Этот канал часто используется теоретиками, поскольку это один из самых простых с шумом для анализа каналов . Многие проблемы теории коммуникации можно свести к BSC. И наоборот, возможность эффективной передачи по BSC может привести к появлению решений для более сложных каналов.

См. также

• Z-канал

Ссылки

• Обложка, Томас М.; Томас, Джой А. (1991). Элементы теории информации . Хобокен, Нью-Джерси: Уайли. ISBN  978-0-471-24195-9 .
• Дж. Дэвид Форни. Составные коды . MIT Press, Кембридж, Массачусетс, 1966.
• Курс Венката Гурусвами [1] Коды, исправляющие ошибки: конструкции и алгоритмы», осень 2006 г.
• Маккей, Дэвид Дж. К. (2003). Теория информации, вывод и алгоритмы обучения . Издательство Кембриджского университета. ISBN  0-521-64298-1 .
• Курс Атри Рудры «Коды, исправляющие ошибки: комбинаторика, алгоритмы и приложения» (осень 2007 г.), лекции 9 , 10 , 29 и 30 .
• Курс Мадху Судана «Введение в алгоритмы теории кодирования» (осень 2001 г.), лекции 1 и 2 .
• Математическая теория связи К. Э. Шеннон, Обзор мобильных вычислений и коммуникаций ACM SIGMOBILE.
• Современная теория кодирования Тома Ричардсона и Рюдигера Урбанке. Издательство Кембриджского университета.