Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
6.5. СВОДКА РЕЗУЛЬТАТОВВ этом разделе мы изложим некоторые аспекты математического анализа метода последовательного декодирования и обсудим основные полученные экспериментальные результаты. АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫТо обстоятельство, что объем
где значение коэффициента
а В тех же условиях из соотношения
Эта оценка сложности не зависит от К и при
Хотя представленные здесь оценки носят частный характер и выбраны скорее из соображений простоты их вывода и формы, а не из-за их точности, они все же позволяют установить три следующих важных свойства последовательного декодирования: 1. При 2. При 3. Хотя поведение величин Таким образом, увеличивая Можно предполагать, что этими тремя свойствами обладают все процедуры последовательного декодирования; они проявляются во всех полученных до сих пор оценках и во всех опубликованных к настоящему времени экспериментальных результатах [48, 78, 91]. ПРЕИМУЩЕСТВА И НЕДОСТАТКИ СИСТЕМЫНеожиданный и основополагающий результат Шеннона, доказавшего, что шумы в канале устанавливают окончательную границу не для точности передачи, а для ее скорости, был впервые опубликован в 1948 г. С тех пор на решение задачи реального повышения надежности передачи было затрачено очень много усилий; предложено много интересных схем кодирования и декодирования. Большинство из них подробно описаны Желание иметь несколько различных решений одной и той же проблемы техники связи обусловлено главным образом инженерными соображениями. Например, рассмотрим гауссовский канал с ограниченной полосой и вычисленный Шенноном для этого канала показатель экспоненты верхней оценки надежности, график которого приведен на фиг. 5.18. Если достаточны умеренная точность и малые скорости передачи данных Чрезвычайно интересным классом кодов, применимым при больших К, являются коды Боуз — Чоудхури — Хоквенгема [15], которые в дальнейшем сокращенно называются БЧХ-кодами. При любом целом числе В качестве примера одного из возможных способов сравнения различных схем декодирования рассмотрим характеристики передачи по гауссовскому каналу с аддитивным белым шумом при применении двоичных БЧХ-кодов и в случае двоичных сверточных кодов при использовании метода последовательного декодирования. Предполагается, что применяются передача противоположными сигналами и симметричное квантование принятого сигнала на два уровня. Результирующая переходная вероятность ДСК равна
где С помощью вычислительной машины можно найти минимальное значение отношения Чтобы сравнить эти результаты с результатами последовательного декодирования, можно использовать соотношение Хотя кривые, приведенные на фиг. 6.49, и поучительны, с точки зрения проектировщика системы связи они никоим образом не могут служить сами по себе основой для решения в пользу того или иного сравниваемого устройства. Следует учитывать также, что разные схемы декодирования обладают различными преимуществами и недостатками в эксплуатации и реализации. Например, до сих пор мы рассматривали лишь среднее количество вычислений, необходимое для последовательного декодирования. В одном из следующих подразделов рассматриваются также флуктуации количества вычислений. Хотя, вообще говоря, БЧХ-коды требуют при декодировании в среднем большего числа операций, чем последовательное декодирование, количество вычислений, которое необходимо провести в случае БЧХ-кодов, гораздо меньше подвержено флуктуациям; во многих приложениях это является ценным преимуществом. Одно из главных достоинств последовательного декодирования — широта области его применимости. Мы уже отмечали, что процедуры последовательного декодирования применимы к широкому классу каналов связи. Характерно, что этот класс включает в себя, в частности, все стационарные дискретные каналы без памяти, т. е. все каналы, у которых статистические связи между используемыми в канале входными и выходными символами могут быть представлены в виде фиксированной диаграммы переходных вероятностей, изображенной, например, на фиг. 6.17. Для любого такого (кликните для просмотра скана) канала оценки, эквивалентные оценкам (6.110) — (6.112), но со значением параметра Отсюда сразу следует, что если в канале с аддитивным белым гауссовским шумом применять не двоичное квантование сигнала на выходе согласованного фильтра, а квантование с очень малым шагом, то можно увеличить предельно достижимую для случая двоичного сверточного кодирования величину
до значений, как угодно близких показателю экспоненты вероятности ошибки в случае отсутствия квантования
При этом улучшается эффективность использования энергии. Если, кроме того, не ограничиваться рассмотрением двоичной передачи, а использовать в передатчике многоамплитудную схему модуляции, получим, как уже отмечалось в гл. 5, значение РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯАналитические трудности при исследовании методов последовательного декодирования таковы, что численная точность даже самых сильных из полученных оценок не достаточна для инженерных целей. В этом и в следующем подразделах будут приведены некоторые результаты моделирования на вычислительной машине алгоритма Фано, проведенного в лаборатории Линкольна Массачусетского технологического института [13]. Работа декодера при передаче по ДСК длинной входной последовательности На фиг. 6.50 приведен график зависимости наблюденного значения Экспериментальные данные, представленные на фиг. 6.50, получены для значений параметра наклона (кликните для просмотра скана) перемещения порога представлено на фиг. 6.51, а, б. Нетрудно заметить, что необходимости в точной минимизации по этим параметрам нет. В заключение следует отметить, что первые символы порождающих последовательностей ДИНАМИКА ПОВЕДЕНИЯ ДЕКОДЕРАХотя из графиков фиг. 6.50 видно, что среднее количество вычислений
Аналитическую оценку Проектирование и оценка систем последовательного декодирования существенно осложняется тем обстоятельством, что количество вычислений подвержено большим флуктуациям. Например, Для сообщений, закодированных соответствующим образом выбранным сверточным кодом, естественно ожидать, что, если не считать редких исключений, искажения символов при передаче по ДСК, как правило, не приводят к тому, что расстояние Хемминга принятой последовательности от действительно переданной будет
Фиг. 6.53. Пример такого изменения меньше, чем от какой-либо из других возможных выходных последовательностей кодера. При этом декодер Фано обычно очень быстро отыскивает правильный путь по кодовому дереву; этим и объясняется малость значения Изредка, однако, искажения символов в канале могут привести к тому, что на значительном протяжении вдоль правильного пути перекошенное расстояние будет увеличиваться с возрастанием Действие шумов в канале, правда, очень редко может привести к тому, что принятая последовательность будет очень близка к одной из возможны
Фиг. где С точки зрения работы декодера необходимо различать ошибки и переполнения. Для наглядности установим разницу между этими явлениями геометрически, рассмотрев фиг. 6.54. Пусть на вход кодирующего устройства поступило в действительности сообщение Для того чтобы последовательный декодер был практически использован, его нужно рассчитать таким образом, чтобы вероятность переполнения и вероятность ошибки били малы. Получение малой вероятности переполнения является более трудной задачей, и мы обсудим ее в первую очередь. Нероятность переполнения. Вероятность переполнения определяется главным образом объемом памяти и вычислительной скоростью декодера. Аналогично величине Чтобы лучше понять поведение вероятности переполнения для алгоритма Фано, рассмотрим процесс декодирования нового символа сообщения, предполагая, что в начале этого декодирования указатель глубины поиска находится в крайнем левом разряде запоминающего устройства, как показано
Фиг. 6.55. Исходное положение декодера, вводимое для упрощения исследования вероятности переполнения. на фиг. 6.55. Пусть максимальное число ребер принятого сигнала, которое может храниться в памяти декодера, равно
В процессе поиска декодер может двигаться назад по кодовому дереву, так что переполнение может наступить раньше, чем будут обследованы На фиг. 6.56, а — в показано типичное поведение длины очереди в случае, когда Малая вероятность переполнения при разумных значениях (кликните для просмотра скана) сообщения и соотношение (6.117) для вероятности переполнения справедливо. Для малых значений вероятности В качестве примера рассмотрим ДСК, для которого
Согласно соотношению (6.117), потребуем, чтобы
или
Если принять, что специализированная декодирующая вычислительная машина затрачивает на обработку одного ребра 7,5 мксек, то получим
что, согласно графику фиг. 6.50, удовлетворяет условию
В этом примере для запоминания каждого принятого ребра требуется 3 двоичных разряда памяти Вероятность ошибки. Так как вероятность переполнения определяется объемом памяти декодера и скоростью вычислений, то ее трудно сделать чрезвычайно малой. Совершенно иначе обстоит дело с вероятностью необнаружимой ошибки. В соответствии с соотношением (6.110) вероятность необнаружимой ошибки для декодера Фано убывает экспоненциально с ростом длины кодовых ограничений К. При условии, что Чтобы лучше почувствовать относительную малость значимости вероятности необнаружимой ошибки, обратимся к фиг. 6.54, где дана геометрическая интерпретация процесса декодирования. Отмеченные продольной штриховкой области, которые соответствуют необнаружимым ошибкам, как правило, включают в себя лишь малую часть из общего числа точек в пространстве принятых сигналов. Кроме того, заштрихованные области
Фиг. 6.57. Геометрическое объяснение того, что полученная нами оценка вероятности ошибки оказывается слабой. Необнаружимая ошибка происходит при передаче вектора обычно далеко удалены друг от друга в смысле расстояния Хемминга и окружены незаштрихованными областями, соответствующими явлению переполнения. Поэтому разумно ояшдать, что если вероятность переполнения мала, то вероятность необнаружимой ошибки ничтожна. Это утверждение было доказано аналитически [28, 78]. Отметим, что убывание вероятности необнаружимой ошибки с ростом К происходит с показателем экспоненты, существенно большим (по абсолютной величине), чем в оценке (6.110), основанной на случайном кодировании. Причина относительной слабости этой последней оценки заключается в том, что теперь мы пренебрегаем возможностью переполнения. На фиг. 6.57 это интерпретируется геометрически. Имеется еще одно до сих пор не обсуждавшееся явление, которое вносит свой вклад в общую вероятность ошибки. Это явление состоит в том, что иногда декодер может принять неправильную гипотезу Избавиться от обнаружимых ошибок можно путем следующей простой модификации декодера: необходимо лишь увеличить длину
Фиг. 6.58. Модификация декодера Фано, позволяющая обнаруживать ошибки. В том случае, когда разряд декодера, из которого выходит гипотетический двоичный символ сообщения, достаточно далеко удален от разряда, при переходе в который указателя глубины поиска происходит переполнение, вероятность того, что переполнение произойдет раньше, чем будет выдана неправильная гипотеза, теперь окажется сравнимой с вероятностью необнаружимой ошибки. Если останавливать декодирование в момент переполнения, то при наличии удлиненного х-регистра общая вероятность ошибки будет настолько мала, что ею можно с уверенностью пренебрегать. ДВУХСТОРОННИЕ СТРАТЕГИИ ПЕРЕДАЧИДля нормальной работы системы последовательного декодирования недостаточно, конечно, чтобы вероятность ошибки была пренебрежимо малой; необходимо также обеспечить, чтобы декодирование возобновлялось автоматически после каждого переполнения. В односторонних системах связи можно достичь этого, периодически прерывая поток символов сообщения на вход кодера передатчика, скажем после каждого блока из С одной стороны, при В случае двухсторонней связи имеется более привлекательная возможность избежать неприятностей, связанных с переполнением. Через определенные
Фиг. 6.59. а) Двухсторонняя система связи. Буферное устройство передатчика сохраняет данные, поступающие в кодер, для их возможной повторной передачи. Предполагается, что символы входного сообщении постоянно доступны на каждом конце. б) Структура потока данных, поступающих в кодер. Заштрихованные интервалы соответствуют вспомогательным символам. Неэаштрихованные интервалы соответствуют обычным символам сообщения. интервалы времени в каждый из двух потоков данных вставляются несколько «вспомогательных» двоичных символов, как это показано на фиг. 6.59. Вспомогательные символы, посылаемые из пункта Важно отметить, что в данной двухсторонней системе связи вспомогательные символы тоже кодируются. Поэтому, даже если оба капала зашум-лены, вероятность неправильного понимания вспомогательного сообщения равна вероятности ошибки декодирования и ею в значительной степени можно пренебречь. Остается, однако, возможность того, что вспомогательное сообщение не будет декодировано вообще. Так как вероятность такого события связана с вероятностью переполнения, ею пренебрегать нельзя. Выходом из положения может служить стратегия «осторожного неудачника», состоящая в том, что если в одном из пунктов принятый блок вообще не был декодирован, передатчик всегда действует так, как будто в действительности была декодирована просьба о повторении передачи. Можно сделать так [88], чтобы при отсутствии необнаружимых ошибок потоки данных, поступающих на каждый кодер, полностью декодировались в соответствующей последовательности без потерь отдельных блоков. Тем самым разрешается проблема недекодированпых блоков, стоявшая в случае односторонней передачи. Стоимость системы возрастает в основном лишь за счет добавления к каждому из передатчиков запоминающего устройства с невысокой скоростью работы, в котором хранятся символы сообщения, поступившие в течение интервала времепи равного сумме промежутков времени, требуемых для двухстороннего обмена сигналами и обработки данных. Каждый цикл «переспрос — повторение» включает в себя «потери» (с точки зрения задачи передачи информации) времени, равные продолжительности двухстороннего обмена сигналами. Иначе говоря, передатчик вновь передает все данные, поступившие и переданные в предыдущий интервал времени, равный Если требуется, чтобы по реальным каналам поддерживалась точная и эффективная связь, необходимость прибегать к двухсторонним системам кажется неизбежной. Параметры большинства каналов меняются во времени, так что их функции надежности флуктуируют. Системы без обратной связи должны быть спроектированы в расчете на эффективную передачу со скоростью, соответствующей наихудшим условиям в канале, поэтому, если условия передачи хорошие, связь становится неэффективной. В случае двухсторонней стратегии, однако, могут быть использованы вспомогательные двоичные символы для того, чтобы потребовать изменения скорости передачи данных. Пример такой системы рассмотрен в следующем подразделе. СХЕМА ЭКСПЕРИМЕНТАЛЬНОЙ СИСТЕМЫВ гл. 5 и 6 мы рассмотрели, как выбор схем модуляции и демодуляции, кодирования и декодирования влияет на помехоустойчивость и сложность системы. Для случая декодирования блоковых кодов по принципу наибольшего правдоподобия это исследование (не включающее вопрос о сложности оборудования) привело нас к оценке
где Для каналов с ограниченной полосой мы обычно измеряли скорость передачи данных в битах за секунду. Если через
где Когда мы рассматривали последовательное декодирование и включили вопрос о сложности декодера в формулировку задачи выбора схемы двухсторонней системы, наши представления о выборе параметров схемы несколько изменились. Выбирая достаточно большое В этой связи отметим также, что допустимую скорость передачи данных определяет величина
то оценку (6.117) для частоты переполнений можно переписать в виде
Поэтому величина При использовании систем последовательного декодирования фундаментальной мерой эффективности схем модуляции и демодуляции является определяемое ими значение параметра Максимизация Межсимвольная интерференция. Искажения сигнала при прохождении по междугородным телефонным линиям в основном вызываются не аддитивным гауссовским шумом, а межсимвольной интерференцией. Если мы попытаемся передать узкий импульс (фиг. 6.60, а), то в действительности примем размазанный импульс большей длительности (фиг. 6.60, б) 1). Размазанность в основном объясняется тем, что фазовая составляющая передаточной функции телефонной линии не является линейной функцией частоты. В результате различные частотные составляющие передаваемого сигнала распространяются с различными скоростями и поэтому достигают приемника с различными задержками. Хотя ширина полосы на уровне 3 дб амплитудной характеристики используемого в эксперименте канала составляла Межсимвольная интерференция может быть в некоторой степени уменьшена путем тщательного выравнивания фаз в линии и формирования передаваемого импульса. Однако, даже если это сделано, при сужении длительности импульса и возрастании частоты повторений импульсов неизбежно возрастает остаточная межеимвольпая интерференция. Если трактовать эту интерференцию как шум, то можно сказать, что увеличение Сигнальные алфавиты. Междугородные телефонные линии обычно характеризуются высоким отношением сигнал/шум. Поэтому, если приняты
Фиг. 6.60. Пример отклика телефонной линии на короткий импульс. соответствующие меры для подавления межсимвольной интерференции, естественно ожидать, что (согласно фиг, 5.17) для максимизации граничного параметра При альтернативных способах выбора Метрика, используемая декодером. Рассмотрим теперь вопрос о выборе подходящей функции расстояния декодера, используемой для проверки гипотез относительно возможного переданного сигнала по принятым данным. Для гауссовского шума обычно используют евклидово расстояние, для шумов в ДСК—расстояние Хемминга. В каждом случае выбор обусловлен, во-первых, соображениями оптимальности используемой меры расстояния, которая оказывается монотонно связанной с апостериорной вероятностью, и, во-вторых, относительной простотой реализации декодера. В нашем эксперименте с телефонной линией наиболее желательным был бы с точки зрения характеристик качества передачи декодер, использующий для вычисления апостериорных вероятностей принятого сигнала при различных гипотезах относительно переданного сигнала эмпирические оценки переходных вероятностей. Значение К счастью, для получения хороших результатов нет необходимости использовать оптимальную систему; в инженерной практике ищут не столько оптимальные решения, сколько стараются избежать вопиющих отклонений от оптимальности. В частности, для рассматриваемого нами каскада, состоящего из модулятора, телефонной линии и демодулятора, результирующий шум характеризуется в первую очередь тем, что вероятности больших искажений амплитуды принятого сигнала гораздо меньше, чем малых. Поэтому интуитивно ясно, что куммулятивная сумма абсолютных разностей напряжений принятого и гипотетического сигналов может служить подходящей, хотя, конечно, и не оптимальной, функцией расстояний при декодировании. Например, если квантованные амплитуды принятого сигнала равны
а гипотетический сигнал
можно определить расстояние между
Функция расстояния, определяемая соотношением (6.121в), монотонно зависит от логарифма апостериорной вероятности, если все сигналы равновероятны и помеха в канале представляет собой аддитивный вектор шума
Конечно, такая модель не может точно описать рассматриваемый нами каскад, состоящий из модулятора, телефонной линии и демодулятора. Однако экспериментальная проверка, выполненная для нескольких различных значений Экспериментальные результаты. После выбора подходящей декодирующей функции расстояния удобный и разумный компромиссный метод оценкисостоит в согласовании функции плотпости, соответствующей этой функции расстояния, с эмпирическими данными, а не в подстановке эмпирических данных непосредственно в соотношение
Фиг. 6.61. Упрощенная блок-схема эксперимента на телефонной линии. объемов алфавита так, чтобы получилось наилучшее согласование с соответствующими экспериментальными данными. Результирующая совокупность экспоненциальных плотностей распределения использовалась затем для вычисления оценки истинного показателя экспоненты вероятности ошибки Длина кодовых ограничений в сверточном кодере, использовавшаяся в этом эксперименте с телефонной линией, была равна В приемнике эта процедура проделывалась в обратном порядке. Общая блок-схема системы представлена на фиг. 6.61. Производились выборки принятого сигнала В этом эксперименте последовательный декодер использовал алгоритм поиска, предложенный ранее алгоритма Фано, и буферное устройство было отделено от самого декодера. Как только каждая из групп, состоящая из 5 символов, декодировалась и выводилась из Скорость передачи данных Вся аппаратура работала круглосуточно в общей сложности 40 час. Средняя скорость передачи во время работы составляла приблизительно 7500 декодированных двоичных символов в секунду. Первая ошибка в декодировании произошла после декодирования более чем 109 двоичных символов сообщения, и эта ошибка была обнаружена после вывода из регистра небольшого числа следующих декодированных символов. Так как задержка между моментом декодирования и моментом выхода двоичного символа из регистра составила всего лишь К бит, то и эта ошибка декодирования не была бы сделана, если бы к х-регистру декодера была добавлена дополнительная задержка, рассчитанная на По-видимому, кодирование лучше всего применять в каналах, в которых обеспечить хорошие условия передачи дорого (или невозможно); описанный выше эксперимент был проведен на телефонной линии главным образом из-за относительной легкости его выполнения. Несмотря на это. экспериментальное изучение использованной нами процедуры позволило лучше понять компромиссы, которые неизбежны при техническом осуществлении кодовых систем связи.
|
1 |
Оглавление
|