Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Shpory_po_TI.doc
Скачиваний:
2
Добавлен:
01.05.2025
Размер:
2 Мб
Скачать
☆

20. Сообщающие коды об ошибках.

По заданному объему кода однозначно определяется число информационных разрядов k. Далее необходимо найти наименьшее n, обеспечивающее обнаружение или исправление ошибок заданной кратности. В случае циклического кода эта проблема сводится к нахождению нужного многочлена g(x).

Начнем рассмотрение с простейшего циклического кода, обнаруживающего все одиночные ошибки.

Обнаружение одиночных ошибок. Любая принятая по каналу связи кодовая комбинация h(x), возможно содержащая ошибку, может быть представлена в виде суммы по модулю два неискаженной комбинации кода f(x) и вектора ошибки ξ(x) :

При делении h(x) на образующий многочлен g(x) остаток, указывающий на наличие ошибки, обнаруживается только в том случае, если многочлен, соответствующий вектору ошибки, не делится на g(x): f(x) — неискаженная комбинация кода и, следовательно, на g(x) делится без остатка.

Вектор одиночной ошибки имеет единицу в искаженном разряде и нули во всех остальных разрядах. Ему соответствует многочлен ξ(x) = хi· Последний не должен делиться на g(x). Среди неприводимых многочленов, входящих в разложении хn+1, многочленом наименьшей степени, удовлетворяющим указанному условию, является x+1. Остаток от деления любого многочлена на x+1 представляет собой многочлен нулевой степени и может принимать только два значения: 0 или 1. Все кольцо в данном случае состоит из идеала, содержащего многочлены с четным числом членов, и одного класса вычетов, соответствующего единственному остатку, равному 1. Таким образом, при любом числе информационных разрядов необходим только один проверочный разряд. Значение символа этого разряда как раз и обеспечивает четность числа единиц в любой разрешенной кодовой комбинации, а следовательно, и делимость ее на х+1.

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

21. Передача информации по дискретному каналу с помехами.

Дискретный канал – канал связи, используемый для передачи дискретных сообщений. Дискретный канал состоит:

- из физической среды передающей сигналы в обе стороны; - из пары канальных сервисных блоков. Дискретные каналы характеризуются: - скоростью передачи (биты в секунду); - величиной помех.

Поскольку в канале с помехами принятому сигналу v может соответствовать передача одного из нескольких сигналов u, то после приема v остается некоторая неопределенность в отношении переданного сигнала. Здесь соответствие между u и v носит случайный характер, поэтому степень неопределенности характеризуется условной апостериорной вероятностью P(ui/vi), причем всегда P(ui/vi) <1. Количество информации, необходимое для устранения оставшейся неопределенности log 1/P(ui/3i), очевидно, равно той части информации определяется как разность:

J(ui,vi)= log 1/P(ui) – log 1/P(ui/vi) = log P(ui/vi)/P(ui)

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

22. Коды исправляющие ошибки

Исправление ошибок (коррекция ошибок)-процедура восстановления информации после чтения её из устройства хранения или канала связи. С кодами, исправляющими ошибки, тесно связаны коды обнаружения ошибок. В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её. По способу работы с данными коды, исправляющие ошибки делятся на блоковые, делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и свёрточные, работающие с данными как с непрерывным потоком. Коды Хемминга - простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром , где  - принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым. Коды Рида-Соломона - недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов. Очень распространены коды Рида-Соломона, работающие с байтами. Свёрточные коды, как правило, порождаются дискретной линейной инвариантной во времени системой. Поэтому, в отличие от большинства блоковых кодов, свёрточное кодирование - очень простая операция, чего нельзя сказать о декодировании.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]