OPISIS_LAB5v2

Рассмотрим простой канал связи, который может передавать и принимать данные со скоростью 512 кбит/с без ошибок. Теперь вы хотите еще больше увеличить скорость передачи данных, и при этом вы начинаете видеть ошибки в приеме. Как разработчик системы связи вы разрабатываете код исправления ошибок, который исправляет эти ошибки при приеме и тем самым увеличивает скорость передачи на 15%. Теперь вы начинаете думать – будут ли другие коды исправления ошибок, которые работают лучше, чтобы вы могли увеличить скорость передачи еще выше? Если да, то какова максимальная скорость, на которую я могу пойти по данному каналу связи? Как мне найти эти коды для исправления ошибок?

Ответы на первые два вопроса дает Шеннон.

Теорема о пропускной способности - тема обсуждения в главе 3. Шеннон показал, что максимальная пропускная способность (скорость передачи) данного канала зависит от двух факторов - доступной полосы пропускания и отношения сигнал / шум. Он показал, как рассчитать максимальную скорость, с которой данные могут быть отправлены по заданному каналу связи с произвольно небольшими ошибками.

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

Самый простой способ добавить избыточности к данным - повторить данные

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

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

исправлением ошибок состоит в том, чтобы максимизировать шансы исправления ошибок при минимизации избыточности.

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

Шеннон показал, что возможны более эффективные коды с исправлением ошибок,

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

Схемы контроля ошибок Схемы контроля ошибок делятся на две большие категории в зависимости от

их применения.

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

приемник запрашивает передатчик для повторной передачи данных.

Схемы прямого исправления ошибок (FEC) добавляют достаточную избыточность прямой передаче, что позволяет получателю исправлять ошибки в полученных данных.

Ключевая идея схем прямого исправления ошибок состоит в том, чтобы позволить приемнику исправлять ошибки передачи самостоятельно. Повторная передача от отправителя не требуется. На рисунке 4 изображена типичная цифровая система связи, использующая схему FEC. Канальный кодер на стороне передатчика добавляет избыточность входящему сообщению на основе выбранного метода исправления ошибок. Выходные данные кодировщика называются кодовыми словами. Кодовые слова модулируются с помощью цифрового модулятора перед их отправкой по каналу связи. Канал может испортить передаваемые данные. Приемник, получив данные, демодулирует их и отправляет в канальный декодер. Канальный декодер использует избыточную информацию и пытается исправить ошибки в полученных данных. После успешного исправления

ошибок избыточная часть данных удаляется, и восстановленное сообщение доставляется в качестве вывода.

Рисунок 4 – Размещение канального кодера и декодера в простой системе связи

На рисунке 4.2 изображена классификация некоторых часто используемых кодов FEC. В зависимости от наличия или отсутствия памяти в структуре кодирования коды FEC в широком смысле классифицируются как блочные коды или сверточные коды.

Рисунок 5 – Классификация кодов прямого исправления ошибок

Канальное кодирование: метрики Как обсуждалось выше, существует несколько типов методов кодирования

каналов, и задача выбора конкретного кода, отвечающего потребностям,

упрощается за счет некоторых показателей. Некоторые из показателей, по которым коды каналов сравниваются друг с другом:

Точность кодирования

Эффективность кодирования

Прирост кодирования

Точность кодирования В цифровой связи качество любой системы оценивается по вероятности

ошибки в битах (BEP), которая может быть оценена путем измерения коэффициента ошибок в битах (BER). BER — это количество битов с ошибкой в потоке из N принятых битов. Чем меньше BER, тем выше точность системы связи.

Качество напрямую связано с BER, который представляет собой статистическую вероятность того, что полученный информационный бит будет обнаружен с ошибкой. В то время как BER — это количественная мера ошибочного приема

битов, BEP — это долгосрочный статистический показатель производительности системы. Когда интервал наблюдения достаточно длинный, то есть, когда количество переданных битов достаточно велико, BER можно рассматривать как приблизительную оценку BEP. В Matlab можно вычислить BER как количество битов, которые не совпадают при сравнении двух потоков данных длины N.

Программа 1: Вычисление BER в Matlab

N=1000;

c=randn(1,N) >0.5 ; %random 1's and 0's as transmitted vector c_cap = randn(1,N) >0.5 ; % consider this as received vector BER = sum((c ~= c_cap))/N; %compute BER

Эффективность кодирования Эффективный код имеет относительно небольшое количество

закодированных битов на символ данных. Он определяется с точки зрения кодовой скорости. Предположим, что каждый входной символ кодера состоит из k бит, а

каждый выходной символ кодера имеет длину n бит n k p , где p -

количество избыточных битов, добавленных кодером. Тогда кодовая скорость определяется как

Чем выше кодовая скорость, тем выше эффективность. Невозможно достичь кодовой скорости, равной единице, поскольку оценки декодера зависят от избыточных битов для исправления ошибок. Уменьшение количества избыточных битов снижает возможность исправления ошибок канальных кодов. Следовательно,

должен быть компромисс между эффективностью кода и возможностью исправления ошибок.

Выигрыш от кодирования Выигрыш от кодирования схемы кодирования определяется как уменьшение

отношения сигнал/шум (SNR) в кодированной системе по сравнению с некодированной системой для того же BER и той же скорости передачи данных.

Рисунок 5 – Измерение выигрыша от кодирования

Ссылаясь на рис. 5, рассмотрим некодированную систему, которая дает BER

10–5 для рабочего SNR 12 дБ. После введения метода кодирования с исправлением ошибок система может достичь того же BER, равного 10–5, при SNR = 10,4 дБ.

Уменьшение рабочего SNR для достижения того же BER называется выигрышем от кодирования. Для данного примера усиление кодирования составляет 1,6 дБ.

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

Обзор блочных кодов Блочные коды строго основаны на арифметике конечных полей и

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

Блочный код контроля ошибок — это набор из M кодовых слов C c0,c1,...,cM 1 , где каждое n-символьное кодовое слово имеет вид c c0,c1,...,cn 1 .

Отдельные координаты кодового слова принимают значения из набора (0,…,q-1)

и выдает кодовое слово шириной n символов формы c c0,c1,...,cn 1 . В этом случае выражения для избыточности и кодовой скорости упрощаются до r n k и

R kn соответственно. С другой стороны, если M qk , кодировщик блоков должен работать с различной длиной блоков.

Для упрощения возьмем случай двоичной передачи, показанный на рисунке

6. При двоичной передаче символы принимают значения из GF(2) , который представляет собой набор, содержащий только два элемента {0,1}. Поток некодированной информации делится на блоки длиной k бит. Кодер блочного кодирования добавляет r избыточных битов к каждому такому блоку, поэтому общая длина вектора кодового слова c c0,c1,...,cn 1 равна n k r битов. Вектор кодового слова передается по каналу аддитивного шума. Ошибки, вносимые каналом аддитивного шума, моделируются как вектор ошибок e e0 ,e1,...en 1 ,

который может принимать случайные значения в векторном пространстве GF(2) .

Рисунок 6 – Иллюстрация процесса блочного кодирования с использованием модели канала основной полосы частот с аддитивным шумом

После приема слова первая задача декодера состоит в том, чтобы проверить и определить, является ли принятое слово допустимым кодовым словом. Если полученное слово не является допустимым кодовым словом, предполагается, что во время передачи произошла одна или несколько ошибок символа. Эта задача называется обнаружением ошибок.

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

Запрос на повторную передачу данных по некоторому протоколу ARQ.

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

Попытка исправить ошибку в полученном слове, применив какое-либо правило декодирования FEC.

Вэтой главе основное внимание уделяется третьему варианту, который применяет правило декодирования FEC для попытки исправления ошибок. В

системе FEC обнаруживаемая комбинация ошибок может заставить декодер выбрать кодовое слово, отличное от того, что было первоначально передано. В

этом случае говорят, что декодер допустил ошибку декодирования. Система FEC

всегда предполагает, что кодовое слово, выбранное декодером, является

правильным. Однако количество шаблонов ошибок, которые могут вызвать

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

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

Возможность обнаружения и исправления ошибок Расстояние – это мера, указывающая на сходство или несходство двух слов.

Для пары слов a a0 , a1,...an 1 и b b0 ,b1,...bn 1 существует множество способов охарактеризовать расстояние d a,b , между двумя словами. Наиболее известны

расстояние Евклида и расстояние Хэмминга. Евклидово расстояние широко применяется при анализе сверточных кодов. Расстояние Хэмминга часто встречается при анализе блочных кодов.

Евклидово расстояние между двумя словами определяется как

Например, расстояние Хэмминга между (0,0,0,1) и (1,0,1,0) в GF(2) равно 3,

поскольку они различаются тремя цифрами. Для модели ошибки с (дискретным)

равномерным распределением амплитуды ошибки наиболее подходящей мерой является расстояние Хэмминга.

Минимальное расстояние блочного кода C — это наименьшее расстояние между всеми парами расстояний кодовых слов в C . Минимальное расстояние блочного кода определяет как его способность обнаруживать ошибки, так и способность исправлять ошибки. Большое минимальное расстояние гарантирует надежность от случайных ошибок. Общая взаимосвязь между минимальным расстоянием между блочным кодом и возможностью обнаружения и исправления ошибок следующая.

Если dmin является минимальным расстоянием Хэмминга блочного кода, код гарантированно обнаружит до e dmin 1 ошибок. Следовательно, пусть c1 и c2

будут двумя ближайшими кодовыми словами в C . Если c1 был передан и c2

получен, ошибка не обнаруживается.

Если dmin является минимальным расстоянием Хэмминга блочного кода и если в приемнике используется оптимальная процедура декодирования ближайшего соседа, код гарантированно исправляет до t dmin 1 / 2 ошибок.

Декодеры для блочных кодов Декодеры для блочных кодов бывают разных видов для приложений, на

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

r c c - декодирование успешно - ошибок приема нет.

r c - ошибка в полученном слове Pe .

c c - ошибка декодера из-за неправильной коррекции Pmc .

c c - необнаруживаемая ошибка Pude .

c ? - сбой декодера. Ошибка обнаружена, но не может быть исправлена.

Декодер может быть спроектирован таким образом, чтобы он никогда не выходил из строя, то есть Pdf 0 . Он всегда декодирует полученное слово в одно из