|
|
Кодовое дерево и решетчатая диаграмма⇐ ПредыдущаяСтр 34 из 34 Еще одним очень наглядным способом описания и иллюстрации работы сверточных кодов является использование так называемого кодового дерева. Рассмотрим сверточный (6.3)–код со схемой, изображенной на рис. 12.8.
На диаграмме рис. 12.9 изображены входные и выходные последовательности кодера: входные – направлением движения по дереву (вверх – 0, вниз – 1), выходные – символами вдоль ребер дерева. При этом кодирование состоит в движении вправо по кодовому дереву. Например, входная последовательность G(x) = (01000 …… кодируется как F = (0011101100000…, последовательность G(x) = (1010100000 … – как F (x) = (1110001000…. Если внимательно посмотреть на строение приведенного на рис. 12.9 кодового дерева, можно заметить, что начиная с четвертого ребра его структура повторяется, т.е. каким бы ни был первый шаг, начиная с четвертого ребра значения выходных символов кодера повторяются. Одинаковые же узлы могут быть объединены, и тогда начиная с некоторого сечения размер кодового дерева перестанет увеличиваться.
Действительно, из рис. 12.9 видно, что, когда третий входной символ вводится в кодер, первый входной символ покидает сдвиговый регистр и не сможет в дальнейшем оказывать влияния на выходные символы кодера. С учетом этого неограниченное кодовое дерево, изображенное на рис. 10.9, переходит в ограниченную решетчатую диаграмму (кодовое дерево со сливающимися узлами) рис. 12.10.
Рис. 12.10 Кодирование сверточными кодами с использованием решетчатой диаграммы, как и в случае с кодовым деревом, представляет собой чрезвычайно простую процедуру: очередные символы входной последовательности определяют направление движения из узлов решетки: если 0, то идем по верхнему ребру, если 1 – по нижнему ребру. Однако в отличие от кодового дерева решетчатая диаграмма не разрастается по ширине с каждым шагом, а имеет начиная с третьего сечения постоянную ширину. В качестве примера закодируем с помощью решетчатой диаграммы несколько информационных последовательностей. Пусть G(x) =(0110000…. Соответствующая ей кодовая последовательность будет иметь вид: F(x) = (001101011100…, или G(x) = (110100 …, тогда F(x) = (1101010010110000…. Рассмотренный механизм кодирования входной кодовой последовательности в свёрточном коде достаточно просто реализуется кодером Трелисса. Треллис-кодирование Рассмотрим принципы треллис–кодирования на основе простейшего кодера, состоящего из двух запоминающих ячеек и сумматоров по модулю два (рис.12.8). Пусть на вход такого кодера поступает со скоростью k бит/с последовательность бит 0101110010. Если на выходе кодера установить ключ DA1, работающий с вдвое большей частотой, чем скорость поступления бит на вход кодера, то скорость выходного потока будет в два раза выше скорости входного потока. При этом считывающая ячейка DA1 за первую половину такта работы кодера считывает данные сначала с логического элемента DD5, а вторую половину такта – с логического элемента DD4. В результате каждому входному биту ставится в соответствие два выходных бита, то есть дибит, первый бит которого формируется элементом DD5, а второй – элементом DD4. По временной диаграмме состояния кодера нетрудно проследить, что при входной последовательности бит 0101110010 выходная последовательность будет 00 11 10 00 01 10 01 11 11 10 (рис. 12.11).
Рис. 12.11. Временные диаграммы работы простейшего кодера Треллиса Отметим одну важную особенность принципа формирования дибитов. Значение каждого формируемого дибита зависит не только от входящего информационного бита, но и от двух предыдущих бит, значения которых хранятся в двух запоминающих ячейках. Действительно, если принято, что Ai – входящий бит, то значение элемента DD5 определится выражением Работу кодера удобно рассматривать на основе не временных диаграмм, а так называемой диаграммы состояния. Состояние кодера будем указывать с помощью двух значений – значения первой и второй запоминающих ячеек DD1 и DD3. К примеру, если первая ячейка хранит значение 1 (Q1=1), а вторая – 0 (Q2=0), то состояние кодера описывается значением 10. Всего возможно четыре различных состояния кодера: 00, 01, 10 и 11. Пусть в некоторый момент времени состояние кодера равно 00. Нас интересует, каким станет состояние кодера в следующий момент времени и какой дибит будет при этом сформирован. Возможны два исхода в зависимости от того, какой бит поступит на вход кодера. Если на вход кодера поступит 0, то следующее состояние кодера также будет 00, если же поступит 1, то следующее состояние (то есть после сдвига) будет 10. Значение формируемых при этом дибитов рассчитывается по формулам
Рис. 12.12. Диаграмма возможных переходов кодера из начального состояния 00 Продолжая аналогичные рассуждения для всех остальных возможных состояний кодера, легко построить полную диаграмму состояний, на основе которой легко вычисляется значение формируемого кодером дибита. Используя диаграмму состояний кодера, несложно построить временную диаграмму переходов для уже рассмотренной нами входной последовательности бит 0101110010. Для этого строится таблица, в столбцах которой отмечаются возможные состояния кодера, а в строках – моменты времени. Возможные переходы между различными состояниями кодера отображаются стрелками (на основе полной диаграммы состояний кодера – рис. 12.13), над которыми обозначаются входной бит, соответствующий данному переходу, и соответствующий дибит. Например, для первого момента времени диаграмма состояния кодера выглядит так, как показано на рис. 12.14. Жирной стрелкой отображен переход, соответствующий рассматриваемой последовательности бит. Продолжая отображать возможные и реальные переходы между различными состояниями кодера, соответствующие различным моментам времени (рис. 12.15), получим полную временную диаграмму состояний кодера (рис. 12.16). Основным достоинством изложенного выше метода треллис–кодирования является его помехоустойчивость. Как будет показано в дальнейшем, благодаря избыточности кодирования (вспомним, что каждому информационному биту ставится в соответствие дибит, то есть избыточность кода равна 2) даже в случае возникновения ошибок приема (к примеру, вместо дибита 11 ошибочно принят дибит 10) исходная последовательность бит может быть безошибочно восстановлена. Для восстановления исходной последовательности бит на стороне приемника используется декодер Витерби.
Рис. 12.13. Полная диаграмма состояния кодера
Рис. 12.14. Временная диаграмма состояния кодера для первого момента времени
Рис. 12.15. Временная диаграмма состояния кодера для двух первых моментов времени
Рис. 12.16. Временная диаграмма состояния кодера для рассматриваемой входной последовательности бит Декодер Витерби Декодер Витерби в случае безошибочного приема всей последовательности дибитов 00 11 10 00 01 10 01 11 11 10 будет обладать информацией об этой последовательности, а также о строении кодера (то есть о его диаграмме состояний) и о его начальном состоянии (00). Исходя из этой информации он должен восстановить исходную последовательность бит. Рассмотрим, каким образом происходит восстановление исходной информации. Зная начальное состояние кодера (00), а также возможные изменения этого состояния (00 и 10), построим временную диаграмму для первого момента времени (рис. 12.17). На этой диаграмме из состояния 00 существует только два возможных пути, соответствующих различным входным дибитам. Поскольку входным дибитом декодера является 00, то, пользуясь диаграммой состояний кодера Треллиса, устанавливаем, что следующим состоянием кодера будет 00, что соответствует исходному биту 0.
Рис. 12.17. Временная диаграмма возможных состояний декодера для первого момента времени Однако у нас нет 100% гарантии того, что принятый дибит 00 является правильным, поэтому не стоит пока отметать и второй возможный путь из состояния 00 в состояние 10, соответствующий дибиту 11 и исходному биту 1. Два пути, показанные на диаграмме, отличаются друг от друга так называемой метрикой ошибок, которая для каждого пути рассчитывается следующим образом. Для перехода, соответствующего принятому дибиту (то есть для перехода, который считается верным), метрика ошибок принимается равной нулю, а для остальных переходов она рассчитывается по количеству отличающихся битов в принятом дибите и дибите, отвечающем рассматриваемому переходу. Например, если принятый дибит 00, а дибит, отвечающий рассматриваемому переходу, равен 11, то метрика ошибок для этого перехода равна 2. Для следующего момента времени, соответствующего принятому дибиту 11, возможными будут два начальных состояния кодера: 00 и 10, а конечных состояния будет четыре: 00, 01, 10 и 11 (рис. 10.18). Соответственно для этих конечных состояний существует несколько возможных путей, отличающихся друг от друга метрикой ошибок. При расчете метрики ошибок необходимо учитывать метрику предыдущего состояния, то есть если для предыдущего момента времени метрика для состояния 10 была равной 2, то при переходе из этого состояния в состояние 01 метрика ошибок нового состояния (метрика всего пути) станет равной 2 + 1 = 3.
Рис. 12.18. Временная диаграмма возможных состояний декодера для первых двух моментов времени Для следующего момента времени, соответствующего принятому дибиту 10, отметим, что в состояния 00, 01 и 11 ведут по два пути (рис. 12.19). В этом случае необходимо оставить только те переходы, которым отвечает меньшая метрика ошибок. Кроме того, поскольку переходы из состояния 11 в состояние 11 и в состояние 01 отбрасываются, переход из состояния 10 в состояние 11, отвечающий предыдущему моменту времени, не имеет продолжения, поэтому тоже может быть отброшен. Аналогично отбрасывается переход, отвечающий предыдущему моменту времени из состояния 00 в 00.
Рис. 12.19. Временная диаграмма возможных состояний декодера для первых трех моментов времени Продолжая подобные рассуждения, можно вычислить метрику всех возможных путей и изобразить все возможные пути. При этом количество самих возможных путей оказывается не так велико, как может показаться, поскольку большинство из них отбрасываются в процессе построения, как не имеющие продолжения (рис. 10.20). К примеру, на шестом такте работы декодера по описанному алгоритму остается всего четыре возможных пути.
Рис. 12.20. Временная диаграмма возможных состояний декодера для четвертого, пятого и шестого тактов
Аналогично и на последнем такте работы декодера имеется всего четыре возможных пути (рис. 12.21), причем истинный путь, однозначно восстанавливающий исходную последовательность битов 0101110010, соответствует метрике ошибок, равной 0.
Рис. 12.21. Временная диаграмма возможных состояний декодера для последнего момента времени При построении рассмотренных временных диаграмм удобно отображать метрику накопленных ошибок для различных состояний кодера в виде таблицы. Именно эта таблица и является источником той информации, на основе которой возможно восстановить исходную последовательность бит (табл. 12.1).
Таблица 12.1. Метрика ошибок для различных состояний декодера
В описанном выше случае мы предполагали, что все принятые декодером дибиты не содержат ошибок. Рассмотрим далее ситуацию, когда в принятой последовательности дибитов содержатся две ошибки. Пусть вместо правильной последовательности 00 11 10 00 01 10 01 11 11 10 декодер принимает последовательность 00 11 11 00 11 10 01 11 11 10, в которой третий и пятый дебит являются сбойными. Попробуем применить рассмотренный выше алгоритм Витерби, основанный на выборе пути с наименьшей метрикой ошибок, к данной последовательности и выясним, сможем ли мы восстановить в правильном виде исходную последовательность битов, то есть исправить сбойные ошибки. Вплоть до получения третьего (сбойного) дибита алгоритм вычисления метрики ошибок для всех возможных переходов не отличается от рассмотренного ранее случая. До этого момента наименьшей метрикой накопленных ошибок обладал путь, отмеченный на рис. 10.22 полужирной линией. После получения такого дибита уже не существует пути с метрикой накопленных ошибок, равной 0. Однако при этом возникнут два альтернативных пути с метрикой, равной 1. Поэтому выяснить на данном этапе, какой бит исходной последовательности соответствует полученному дибиту, невозможно.
Рис. 12.22. Вычисление метрики накопленных ошибок при получении первого ошибочного дибита Аналогичная ситуация возникнет и при получении пятого (также сбойного) дибита (рис. 10.23). В этом случае будет существовать уже три пути с равной метрикой накопленных ошибок, а установить истинный путь возможно только при получении следующих дибитов. После получения десятого дибита количество возможных путей с различной метрикой накопленных ошибок станет достаточно большим (рис. 12.24), однако на приведенной диаграмме (с использованием табл. 12.2, где представлена метрика накопленных ошибок для различных путей) нетрудно выбрать единственный путь с наименьшей метрикой (на рис. 12.24 этот путь отмечен жирной линией). По данному пути, пользуясь диаграммой состояния треллис–кодера (см. рис. 12.13), можно однозначно восстановить исходную последовательность бит 0101110010, невзирая на допущенные ошибки при получении дибитов.
Рис. 12.23. Вычисление метрики ошибок при получении второго ошибочного дибита
Рис. 12.24. Вычисление метрики ошибок при получении последнего дибита Рассмотренный сверточный кодер Треллиса на четыре состояния и алгоритм Витерби являются простейшими примерами, иллюстрирующими основной принцип работы. В реальности используемые кодеры Треллиса (и в гигабитных адаптерах, и в модемах) гораздо более сложные, но именно благодаря их избыточности удается значительно повысить помехоустойчивость протокола передачи данных.
Таблица 12.2. Метрика накопленных ошибок для различных путей
Контрольные вопросы 1. Сформулируйте теорему Шеннона о кодировании в каналах связи с помехами. 2. Перечислите основные задачи, решаемые кодированием. 3. При каких предположениях решают задачи корректирующего кодирования? 4. Приведите классификацию корректирующих кодов. 5. Дайте определение блочным кодам. 6. Назовите основные характеристики корректирующих кодов. 7. Покажите принцип обнаружения ошибок на геометрической модели кодов. 8. Приведите выражение для определения числа контрольных символов. 9. Какие коды называются систематическими? 10. Как строится образующая и проверочная матрицы систематического кода? 11. Как получается алгоритм кодирования и декодирования в систематическом коде? 12. Какой принцип кодирования кодовых комбинаций в рекуррентном коде? 13. Какое минимальное расстояние должно быть между пакетами искажений, чтобы принятая кодовая комбинация была однозначно декодируемой? 14. Поясните принцип работы кодера сверхточного кода (8,4). 15. Приведите и поясните диаграмму переходов кодера (6,3). 16. В чём сущность декодирования кодовых сообщений по методу Витерби. ЗАКЛЮЧЕНИЕ Изложенные в конспекте лекций идеи и методы теории информации представляют интерес не только в плане решения задач, связанных с передачей и хранением информации. Теоретико–информационный подход приобрел значение метода исследования, позволяющего качественно и количественно сопоставлять специфические характеристики конкретных устройств и систем независимо от их физической сущности. Трудами ученых и инженеров созданы и продолжают создаваться фундаментальные методы анализа, синтеза и оптимизации информационных систем. Развивается математическое моделирование процессов передачи сообщений, разрабатываются и внедряются новые методы анализа нестационарных непрерывных каналов, неоднородных асимметричных дискретных каналов, помехоустойчивые методы и алгоритмы передачи информации, в которых учитывается ненадежность аппаратуры и отклонение характеристик устройств от идеальных, строятся математические модели сложных шумовых ситуаций, интенсивно развивается корректирующее кодирование. Методы теории информации все шире применяются для решения практических задач повышения качества передачи информации и эффективности систем и сетей связи, радионавигационных и радиолокационных систем, автоматизированных систем управления воздушным движением, вычислительных систем, измерительных комплексов и многих других. Основные тенденции и перспективы теории информации следующие: широкое внедрение цифровых методов передачи сообщений; рост удельного веса алгоритмических и программных методов управления процессами передачи информации; широкое использование корректирующего кодирования; разработка методов оценки эффективности передачи информации с позиции системного подхода; применение цифрового и статистического моделирования процессов передачи сообщения для анализа и синтеза информационных систем; Глубокое и всестороннее развитие теории информации тесно связано с практическими потребностями информационной техники. Следует ожидать, что идеи и методы теории информации будут успешно использоваться при создании сложных систем, объединяющих различные по целям, функциям и даже физическому воплощению подсистемы.
ЛИТЕРАТУРА
1. Дмитриев В. И. Прикладная теория информации.–М.:Высш.шк.,1989.–320 с. 2. Темников Ф.Е. и др. Теоретические основы информационной техники.–М.: Энергия, 1979.–512 с. 3. Герасименко В.А., Мясников В.А. Защита информации от несанкционированного доступа.–М.: МЭИ, 1984. 4. Шеннон К. Работа по теории информации и кибернетике.–М.: ИЛ, 1963. 5. Питерсон У.,Уэлдон Э. Коды, исправляющие ошибки.–М.: Мир, 1976. 6. Игнатов В.А. Теория информации и передачи сигналов: Учебник для вузов.–М.:Сов.радио,1979.–280с. 7. Пенин П.И., Филиппов Л.И. Радиотехнические системы передачи информации: Учеб. пособие для вузов.–М.:Радио и связь, 1984.–256 с. 8. Фельдбаум А.А. и др. Теоретические основы связи и управления.–М.: Физматгиз, 1963.–932 с. 9. Шувалов В.П. и др. Передача дискретных сообщений: Учебник для вузов.–М.: Радио и связь, 1990.–464 с. 10. Бовбель Е.И. и др. Элементы теории информации.–Мн.: БГУ, 1974.–111 с. 11. Ильин В.А. Телеуправление и телеизмерение: Учеб. пособие для вузов.–3–е изд.–М.: Энергоиздат, 1982.–560 с. 12. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си.–М.: Изд–во ТРИУМФ, 2002.–816 с. 13. Столлингс Вильям. Криптография и защита сетей.–М., 2002. 14. Молдовен и др. Криптография. Скоростные шифры. –М., 2003. 15. Маслянников М. Практическая криптография.–М., 2003. 16. Петраков А.В., Лагутин В.С. Телеохрана.–М.: Энергоатомиздат, 1998.–376 с. 17. Основы теории передачи информации. ч.1. Экономное кодирование. /В.И.Шульгин. – Учебн.пособ. – Харьков: Нац. аэрокосм. ун–т «Харьк. Авиац. Ин–т.», 2003–102с. 18. Основы теории передачи информации. ч.2. Экономное кодирование. /В.И.Шульгин. – Учебн.пособ. – Харьков: Нац. аэрокосм. ун–т «Харьк. Авиац. Ин–т.», 2003–87с. 19. Лидовский В.В, Теория информации: Учебное пособие. – М.: Компания Спутник +, 2004.–111с.
  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
Соответствующее этому кодеру кодовое дерево – последовательность выходных состояний кодера при подаче на его вход цепочки входных символов 0 и 1 – приведено на рис. 12.9.
Другими словами, выходная кодовая последовательность в определенный момент перестает зависеть от значений входных символов, введенных в кодер ранее.
, а значение элемента DD4 – выражением 
. Таким образом, дибит формируется из пары битов, значение первого из которых равно 
, а второго – 
), если же на вход поступает 1, то формируется дибит 11 (
). Приведенные рассуждения удобно представить наглядно с помощью диаграммы состояний (рис. 10.12), где в кружках обозначаются состояния кодера, а входящий бит и формируемый дибит пишутся через косую черту. Например, если входящий бит 1, а формируемый дибит 11, то записываем: 1/11.
