74. Математическая модель дискретного канала с помехами.
*см вопрос 27
75 Коды Рида-Соломона
Коды Рида-Соломона широко применяются в цифровой технике. Они обладают определенными оптимальными свойствами и для них разработаны относительно простые и конструктивные методы кодирования. Коды Рида-Соломона не являются двоичными. Это надо понимать в том смысле, что символами кодовых слов являются не двоичные знаки, а элементы множества чисел, состоящего более чем из двух знаков (хотя, конечно, при передаче или записи каждый символ кодового слова заменяется соответствующей двоичной комбинацией).
Коды Рида-Соломона относятся к классу циклических кодов. Кодирование и декодирование, обнаруживающее и исправляющее ошибки, - это вычислительные процедуры, которые для циклических кодов удобно выполнять как действия с многочленами и которые допускают относительно простую схемотехническую реализацию в виде цифровых автоматов на базе регистров с обратными связями.
Если кодируемая информация i описывается набором (блоком) из k символов, то этому набору, или слову можно поставить в соответствие информационный многочлен
i(x)=ik-1xk-1+ik-2xk-2+...+i1x1+i0.
Так как цель кодирования - исправление ошибок, достигаемое благодаря введению избыточности, то каждому информационному слову должно соответствовать кодовое слово c=(cn-1, cn-2, ..., c1, c0) большей длины с добавленной избыточностью в виде дополнительных символов. Это кодовое слово также можно записать в виде многочлена
c(x)=cn-1xn-1+cn-2xn-2+...+c1x+c0.
В соответствии с теорией циклических кодов образование кодовых слов производится с помощью порождающего многочлена, степень которого равна числу дополнительных (проверочных) символов:
g(x)=gn-kxn-k+gn-k-1xn-k-1+...+g1x+g0.
Процедура нахождения кодового слова заключается в умножении информационного многочлена на порождающий многочлен кода. Таким образом, отличительной особенностью всех кодовых слов является то, что они получены умножением разных информационных многочленов на один и тот же порождающий многочлен. Следовательно, они все делятся на порождающий многочлен без остатка. Это обстоятельство дает ключ к декодированию, позволяющему обнаруживать и исправлять ошибки, возникшие при передаче данных. Слова, которые не делятся без остатка на порождающий многочлен, не являются кодовыми и, следовательно, содержат ошибки. Теория кодов Рида-Соломона показывает, что если цель кодирования - исправить t ошибок в кодовом слове, то степень порождающего многочлена (n-k)=2t. Следовательно, кодовое слово должно содержать два дополнительных символа на одну исправляемую ошибку. Для создания нового кода с заданными свойствами надо образовать соответствующий порождающий многочлен.
76. Теорема Котельникова (основная теорема Шеннона)
Теорема Котельникова — Шеннона (теоре́ма Коте́льникова) гласит, что, если аналоговый сигнал x(t) имеет спектр, ограниченный частотой Fmax, то он может быть однозначно и без потерь восстановлен по своим дискретным отсчётам, взятым с частотой:
fдискр>=2Fmax
где Fmax — верхняя частота в спектре, или, по-другому, по отсчётам, взятым с периодом:
Tдискр<=1/(2Fmax)
Теорема была сформулирована В. А. Котельниковым в 1933 году в его работе «О пропускной способности эфира и проволоки в электросвязи» и является одной из основополагающих теорем в теории и технике цифровой связи.
Говоря шире, теорема Котельникова говорит о том, что непрерывный сигнал можно представить в виде следующего ряда:
Под интегральной суммой написана формула отсчетов фунцкии x(t). Мгновенные значения этой функции есть значения дискретизированного сигнала в каждый из моментов времени.