Помехоустойчивое кодирование: различия между версиями

Нет описания правки
(Пробую автоматически получить из TeXa викиразметку)
проводом. Под проводом следует понимать любую физическую среду
передачи данных. Посредством этой физической среды
нужно научиться передавать биты так, чтобы они безошибочно
принимались получателем точно в той последовательности,
в какой они были переданы.
==Канальный уровень==
 
На уровне канала данных решается ряд проблем, присущих
только этому уровню:
* реализация сервиса для сетевого уровня,
получения кадра. Недостатком этого метода является
зависимость от кодировки (кодозависимость).
 
По мере развития сетей эта связь становилась все более и более
обременительной и был предложен новый очевидный кодонезависимый
метод — управляющие последовательности должны быть
:<math>\Omega_{in}=\{x_1,\dots, x_a\},\;\Omega_{out}=\{y_1,\dots, y_b\},</math>
 
то канал определяется матрицей условных вероятностей
<math>\|r_{ij}\|</math>, <math>r_{ij}</math> — вероятность того, что на выходе
будет значение <math>y_i</math> при условии, что на входе измерено
\end{figure}
\end{center}
Построение конкретных способов кодирования, приближающихся
по пропускной способности к теоретической границе —
сложная математическая задача.
</math>
 
Например, при <math>n=1000</math> и <math>p=10^{-6}</math> получаем <math>P_{miss}\approx 4.99\cdot 10^{-7}</math>
4.99\cdot 10^{-7}</math>
\end{task}
 
Следующая задача повышенной сложности.
 
\begin{task}[*]
\label{task:errmod} Пусть у нас есть возможность контролировать
</math>
 
''Примечание.'' Интерес здесь представляет неявно
заданная функция <math>n(d,P_{miss},p)</math>, а точнее даже коэффициент
содержания полезной информации
 
:<math>\rho_H(10001001,10110001)=3.</math>
 
 
\begin{task}
Докажите, что <math>\rho_H</math> метрика.
\end{task}
 
Если два слова находятся на расстоянии <i>r</i> по Хеммингу,
это значит, что надо инвертировать ровно <i>r</i> разрядов, чтобы
между двумя различными допустимыми кодовыми словами
называется ''расстоянием Хемминга данного кода''.
 
\label{simplecode}
 
Элементарный пример помехоустойчивого кода — это код, у
которого есть только четыре ''допустимых кодовых
<math>G(x)</math> равна <i>l</i>. Тогда длина блока &laquo;конторольной суммы&raquo; также
равна <i>l</i>.
 
Мы добавляем контрольные <i>l</i> бит в конец передаваемого
блоку так, чтобы получился полином кратный генератору
<math>G(x)</math>. Когда получатель получает блок с контрольной суммой,
\begin{task}
\label{task:err}
Мы хотим передавать информацию блоками, которые содержали
бы <i>m</i> бит полезной информации, так, чтобы
вероятность ошибки в одном бите равнялась <i>p</i>, а
правильность передачи &laquo;фиксировалось контрольной суммой&raquo;. Найти
минимальный размер блока <math>n(m,p)</math> и коэффициент раздувания
<math>k=\frac{n(m)}{m}</math>.
\end{task}
\pb''Решение.''
Для передачи <i>m</i> бит с вероятностью ошибки в отдельном бите
<i>p</i> требуется передать <math>m C(p)</math> бит
<math>H((1-p)^m)</math>. В итоге получаем <math>n=mC(p)+H((1-p)^m)</math> и
 
:<math>k(m,p)=C(p)+\frac{H((1-p)^m)}{m}.\pe</math>
 
''Конец решения.''
 
Заметим, что <math>k(1,p)=1</math> — когда блок имеет размер один бит,
ошибочной передачи блока при условии, что &laquo;контрольная сумма
сошлась&raquo; и кадр засчитан правильно переданным.
Такое выражение для <math>KPS_{\varepsilon}(p,n)=\frac{m}{n}</math>
получается из формулы
 
481

правка