Содержание к диссертации
Введение
1. Анализ алгоритмов помехоустойчивого кодирования, современных методов коррекции ошибок, энергетической эффективности 11
1.1 Основные принципы помехоустойчивого кодирования 11
1.2 Анализ преимуществ и недостатков кодов в современных системах связи 14
1.3 Аппаратная реализация помехоустойчивого кодирования в кодерах/декодерах 19
1.4 Преимущества турбо кодов произведения и их аппаратная реализация. 34
1.5 Аппаратная реализация многопороговых декодеров 42
1.6 Цель и задачи исследования 43
1.7 Выводы первой главы 45
2. Разработка математических моделей модифицированного алгоритма витерби 47
2.1 Математическая реализация модицицированного многовариантного алгоритма Витерби 47
2.2 Особенности реализация модифицированного алгоритма Витерби на ПЛИС для протоколов у.42 и у.32 56
2.3 Энергетическая эффективность многовариантного декодера 62
2.4 Разработка и применение многовариантного алгоритма в алгоритме Витерби 64
2.5 Основные выводы второй главы 68
3. Разработка алгоритмов реализации модифицированного многоуровневого алгоритма витерби для реализации на плис 70
3.1 Особенности функционирования последовательных и параллельных алгоритмов. 70
3.2 Разработка алгоритма реализации многоуровневого алгоритма Витерби для протоколов v.32 И v.42 72
3.3 Алгоритм декодирования Витерби для реализации на ПЛИС 77
3.4 Основные выводы третьей главы 81
4. Аппаратная реализация кодеров на базе модифицированного алгоритма витерби на плис 82
4.1 Характерные преимущества модифицированного алгоритма Витерби по сравнению с общепринятыми кодами при аппаратной реализации на ПЛИС. 82
4.2 Структурная схема декодера на ПЛИС, реализующего модифицированный алгоритм Витерби .
4.3 Синтез аппаратных модулей декодера на ПЛИС, реализующего модифицированный алгоритм Витерби. 90
4.4 Энергетический выигрыш модифицированного алгоритма Витерби с увеличением вычислительной сложности и без увеличения. 92
4.5 Основные выводы четвертой главы 94
Заключение 95
Список источников 96
- Аппаратная реализация помехоустойчивого кодирования в кодерах/декодерах
- Особенности реализация модифицированного алгоритма Витерби на ПЛИС для протоколов у.42 и у.32
- Разработка алгоритма реализации многоуровневого алгоритма Витерби для протоколов v.32 И v.42
- Структурная схема декодера на ПЛИС, реализующего модифицированный алгоритм Витерби
Введение к работе
Актуальность темы. Системы цифровой передачи информации играют важную роль в современном мире, и требования к скорости и надежности передаваемых данных постоянно растут. В стационарных системах связи аддитивный шум и межсимвольная интерференция (МСИ) являются основными факторами, которые приводят к появлению ошибок при передаче данных по каналу связи. Реализация современных помехоустойчивых систем передачи цифровой информации невозможна без применения кодеков, выполненных по современной технологии, способных работать на высоких тактовых частотах, что позволяет повысить эффективность использования аппаратной реализации, энергетическую эффективность, помехоустойчивость, а также положительно сказывается на экономическом эффекте.
Кодеры и декодеры помехоустойчивых кодов являются наиболее ресурсоемким компонентом аппаратуры, особенно с ростом скорости передачи информации. Существенная часть сложности и стоимости заложена в них.
Для повышения энергетической эффективности и исправления ошибок практически во всех современных цифровых системах применяется помехоустойчивое кодирование цифровых сигналов. Причина этого кроется в дефиците частотного ресурса, применение помехоустойчивого кодирования позволяет работать при меньшем соотношении сигнал-помеха, что позволяет более плотно размещать абонентов и уменьшить количество частот в сотовых системах связи. Важной проблемой является недостаток пропускной способности каналов связи. Одним из путей решения этой задачи является использование помехоустойчивого кодирования сигналов. Алгоритмы декодирования применимы и в случае использования демодулятора с мягкими решениями на входе, что позволяет достичь максимально возможного энергетического выигрыша от декодирования.
Хотя в перспективных системах делается упор на использование турбо-кодов и LDPC кодов (код с малой плотностью проверок на чётность, от англ. Low-density parity-check code), тем не менее существует множество телекоммуникационных систем, использующих сверточный код.
Сверточный код достаточно широко распространен, поэтому повышение эффективности его декодирования является актуальной задачей. Во многих системах действует автоматическая регулировка мощности, автоматическая регулировка параметров модуляции, поэтому улучшение параметров приемника приведет к улучшению всей системы в целом – передатчик снизит мощность при отсутствии ошибок.
Алгоритм Витерби является одним из эффективных и наиболее распространенных среди алгоритмов декодирования сверточного кода, основанный на работе с решетчатой диаграммой, поскольку он позволяет получить максимально правдоподобную (МП) оценку переданного кодового слова. Основным недостатком алгоритма декодирования Витерби является экспоненциальный рост вычислительной сложности при увеличении числа внутренних состояний декодера.
Стандартные декодеры, реализующие алгоритм Витерби, не позволяют добиться требуемых показателей надежности и качества, а также помехоустойчивости.
Повышение эффективности и помехоустойчивости декодирования является важной задачей при проектировании современных помехоустойчивых систем передачи цифровой информации. Таким образом, актуальность диссертационной работы определяется необходимостью разработки математических моделей, алгоритмов и методик, позволяющих повысить энергетическую эффективность и помехоустойчивость декодирования посредством модифицированного алгоритма Витерби.
Работа выполнена в рамках одного из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» «Перспективные радиоэлектронные и лазерные устройства и системы передачи, приема, обработки и защиты информации» и ГБ НИР 2007.17 «Методы исследования и повышения надежности и качества при проектировании радиоэлектронных устройств и систем».
Цель и задачи исследования. Целью диссертационного исследования является разработка моделей и методов построения декодеров на базе модифицированного алгоритма Витерби.
Для достижения поставленной цели необходимо решить следующие основные задачи:
провести анализ существующих алгоритмов помехоустойчивого декодирования, с целью оценки их эффективности и помехоустойчивости декодирования сверточного кода в цифровых каналах связи;
выбрать методы эффективной модификации алгоритма Витерби, позволяющей повысить эффективность его работы в турбо-декодерах, с точки зрения энергетической эффективности и высокой вероятности исправления ошибок без увеличения вычислительной сложности;
разработать методику реализации помехоустойчивого алгоритма Витерби для протоколов связи V.32 с модулем, реализующим коррекцию ошибок по протоколу V.42;
предложить математические модели функционирования помехоустойчивого, энергоэффективного алгоритма, на базе которого строится декодер;
разработать модифицированный алгоритм декодирования, отличающийся возможностью обнаружения и коррекции ошибок при передаче цифрового сигнала.
Методы исследования. При выполнении работы использованы принципы системного анализа, методы математического моделирования цифровых интегральных схем, методы обработки и математического моделирования цифрового сигнала, элементы теории чисел с плавающей арифметикой, методы помехоустойчивого кодирования.
Научная новизна результатов исследования. В работе получены следующие результаты, характеризующиеся научной новизной:
модифицированный многовариантный алгоритм Витерби, отличающийся повышением энергетической эффективности декодера, за счет взаимодействия данного алгоритма с модулем коррекции ошибок в существующих системах связи;
многовариантный алгоритм декодирования, отличающийся возможностью проводить коррекцию ошибок при передаче цифрового сигнала, что позволяет повысить помехоустойчивость системы за счет использования вычислительных ресурсов приемника, выделенных на помехоустойчивое декодирование;
модель помехоустойчивого декодера, построенного на базе модифицированного алгоритма Витерби для протоколов связи V.32 с модулем коррекции ошибок V.42, отличающаяся повышением эффективности обнаружения ошибок, без увеличения вычислительных мощностей, за счет распараллеливания циклов поиска верного пути;
методика построения декодеров на базе модифицированного алгоритма Витерби, отличающаяся использованием технологии компонентно-модульного синтеза блоков декодера на ПЛИС, позволяющая повысить помехоустойчивость за счет увеличения вычислительной сложности приемника.
Практическая значимость. На основе предложенных моделей и алгоритмов разработан модифицированный алгоритм Витерби, позволяющий повысить энергетическую эффективность, помехоустойчивость и быстродействие декодеров.
Использование этого алгоритма позволяет значительно повысить энергетическую эффективность и быстродействие кодеров на ПЛИС, реализующих модифицированный алгоритм Витерби, применяемых в системах помехоустойчивого кодирования приема-передачи цифрового сигнала, что позволяет значительно повысить экономические показатели производства.
Основные положения диссертации внедрены в ОАО «Концерн «Созвездие» и в учебный процесс кафедры КИПР ФГБОУ ВПО "ВГТУ".
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях, совещаниях и семинарах: Международной конференции «Системные проблемы надежности, качества, информационных и электронных технологий» (Сочи, 2007-2010); Всероссийской научно-технической конференции молодых ученых «Современные проблемы радиоэлектроники» (Красноярск, 2007-2010); ежегодных научно-технических конференциях ГОУ ВПО «Воронежский государственный технический университет» и научно-методических семинарах кафедры конструирования и производства радиоаппаратуры (2007-2010).
Публикации. По теме диссертации опубликовано 10 научных работ, в том числе 3 - в издании, рекомендованном ВАК РФ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы, включающего 113 наименований, приложений. Основная часть работы изложена на 111 страницах, содержит 52 рисунка и 8 таблиц.
Аппаратная реализация помехоустойчивого кодирования в кодерах/декодерах
Цифровой код являет из себя некую форму представления сообщения, не зависящую от его физической сущности, что является отличительной чертой, отличающую код от сигнала и определяющий физическое представление сообщения (и кода) в системе связи. Однако, в реальности зачастую связываются абстрактная (символьная) форма кода с физическими сигналами. Код представляется как совокупность кодовых символов; помехоустойчивый код дает возможность находить и/или корректировать ошибки во всей последовательности кодовых сигналов /30,31/.
При условии обладания сообщениями коррелирующими связями, т. е. если одна символьная последовательность определенным способом зависит от другой последовательности, что обычно встречается при передаче текстовых сообщений на лингвистических языках, то помехозащищенность любого кодирующего алгоритма можно повысить благодаря наличию смысловых связей между словами в передаваемых сообщениях. При условии, что между словами связь слабая, или она неизвестна, или ее не представляется возможным использовать для усиления помехостойкости, то при таком варианте способ представления сообщений должен обладать избыточностью; а именно, искусственно увеличивают количество символов в сообщении, а меж кодовых последовательностей добавляют априори известных корреляционных связей. По этому причине помехозащищенные коды являются избыточными кодами. При введении избыточности в кодовую последовательность помимо детектирования и коррекции ошибок, также позволяет повысить энергетическую эффективность каналов связи, сократить количество частот, уменьшить время установления связи посредством увеличения помехозащищенности блоков синхронизации. Структура системы связи определяет вид, который имеет помехоустойчивый код. Общая структурная схема которого изображена на рис. 1.2. Рассматриваются линии связи, по которым передаются данные дискретно. В современных цифровых системах дискретные данные поступают на вход от нескольких источников. Имея один внешний источник, в системе связи содержится служебный источник сигналов, телеуправления (ТУ) и телесигнализации (ТС). Сообщения от разных источников могут поступать как с одинаковой скоростью, так и асинхронно со своей тактовой частотой. Блок уплотнения (БУ) соединяет блоки данных, поступающие с разных источников, в одну общую последовательность двоичного кода с тактовой частотой, равной скорости передачи самой линии связи /33,34/.
Структурная схема системы связи Данные от источников информации (ИИ) поступают в блок уплотнения сообщений (БУ), после чего информация кодируется кодером, состоящим из внешних (КДШ) и внутренних (КДВ) кодеров, внешних (ПРШ) и внутренних (ПРВ) перемежителей. Затем с выхода кодера поток данных поступает в модулятор (М) и передаются передатчиком (ПД) в линию связи (ЛС). Часто возникающая ошибка в одном бите кода ведет к возникновению ошибки и в соседних символах этой последовательности, что приводит к возникновению блока с ошибочными битами на входе декодирующего устройства с модулем коррекции ошибок. Если кодирующий алгоритм подразумевает исправление Т-ошибок в последовательности из N бит, а совокупность ложных ошибочных битов больше чем Т, то в таком случае декодер не сможет исправить ошибки. После того как данные принимаются приемником (ПР) они поступают в демодулятор (Д), с выхода которого поступают на вход АЦП -аналогово-цифровой преобразователь. Далее данные декодируются декодером, состоящим из блоков додетекторного сложения БДС, последетекторного сложения БПС. Затем цифрой поток данных направляется в блок разуплотнения сообщений (БР) и выдается получателю информации (ПИ).
В случае, когда скорость принятия сообщений от источников не равны относительно тактовой частоты системы связи, блок уплотнения сообщений начинает асинхронно вводить сообщения. Чтобы различать сообщения на приемной стороне при уплотнении данных, блок уплотнения добавляет специальный флаг, помечающий на каком месте находится первый источник в общем потоке информации. Этот флаг периодически повторяется, тем самым образует сигнал цикличной синхронизации. Устройство кодирования вносит избыточные биты данных в двоичный поток символов, при этом кодирование информации будет выполняться итерационно в соответствии с этапами различными кодерами, коррелируя с требуемой степенью помехоустойчивости.
Особенности реализация модифицированного алгоритма Витерби на ПЛИС для протоколов у.42 и у.32
Последовательность комплексных символов с выхода демодулятора по ступает на вход помехоустойчивого декодера. Первые два бита выходного символа декодера поступают на вход дифференциального декодера (предполагается, что помехоустойчивый декодер сам преобразовывает комплексный символ в битовый набор и удаляет избыточный бит). Два выходных бита дифференциального декодера и не попавшие в него незащищенные биты символа последовательно поступают на вход дескремблера. Затем выходные биты дескремблера обрабатываются модулем v.42 и предоставляются пользователю.
Особенностью обработки данных при их передаче согласно стандарту v34 111 является то, что преобразование выходных символов помехоустойчивого декодера в биты производится для непересекающихся четверок следующих друг за другом символов распределяющих фреймов (mapping frame). Количество передаваемых бит в каждом распределяющем фрейме также не является постоянным, а определяется номером данного распределяющего фрейма во фрейме данных (data frame). Существует только два возможных числа передаваемых бит на один распределяющий фрейм, поэтому для сохранения информации о количестве бит в каждом распределяющем фрейме используется очередь из булевых переменных (состояния фреймов).
Особенностью стандарта передачи данных v34 является то, что символы декодера являются четырехмерными. Четырехмерные символы состоят из непересекающихся пар соседних комплексных (двумерных) символов. Четырехмерные и двумерные символы разделены на восемь групп, при этом сочетание номеров групп для двух двумерных символов, из которых состоит четырехмерный символ, определяет номер группы последнего. Переходу помехоустойчивого кодера из состояния в состояние соответствует определенный номер группы, т. е. неправильный выбор четырехмерного символа группы приводит к возникновению параллельного перехода, который не может быть исправлен стандартным декодером Витерби. Неправильный выбор двумерного символа группы в дальнейшем однозначно приводит к неправильному выбору четырехмерного символа и, как следствие, также к появлению ошибок на выходе стандартного декодера Витерби. Данные об энергетическом выигрыше многовариантного декодера сведены в таблицу 2.1 Таблица 2.1 - Энергетический выигрыш при использовании многовариантного декодера Уровень вероятности ошибки, Рь Энергетический выигрыш, дБ V.32bis V.34 М=2 М=4 М=2 М-4 ю-4 0,8 1,1 0,5 0,8 10 5 0,8 1,2 0,6 0,9 Полученные расчетным путем результаты позволяют сделать вывод о том, что за счет реализации предложенной идеи взаимодействия, путем увеличения вычислительной сложности алгоритма работы приемника можно повысить энергетическую эффективность рассмотренных систем связи примерно на 1 дБ.
Задача помехоустойчивого декодера состоит в формировании оценки с переданной информационной последовательности с по зашумленной последовательности г = х + п. В том случае, если задача декодера состоит в минимизации средней вероятности перепутывания переданной и декодированной информационных последовательностей, декодер должен выбрать решение согласно правилу максимума апостериорной вероятности (МАВ) /4, 12/. При заданных статистических свойствах информационной последовательности с все кодовые слова являются равновероятными, и правило МАВ переходит в правило максимума правдоподобия (МП). МП оценкой переданной информационной последовательности является последовательность c = argmax(P(rc)) , где Р(г\с) — функция правдоподобия: Р{т I с) = Р(г v) = Р(г 1 х) = ЦЦ (-\ - - . 17(2 т2)) п 10) В том случае, если необходимо минимизировать среднюю вероятность перепутывания переданной и оцененной последовательностей данных, на приемной стороне необходимо формировать оценку согласно правилу МАВ /4, 12/.
При заданных статистических свойствах передаваемых данных все последовательности являются равновероятными, и правило МАВ переходит в правило МП/94,95,96/. МП оценкой переданной последовательности данных является последовательность с = argmax(P(r а)), где P(r а) — функция правдоподобия: р(га)=Й72кехр(ЧГі-І л2/(2 72)) (2лі) N- длина последовательности данных, а2 дисперсия шума
Таким образом, задача оценки переданной последовательности данных по правилу МАВ сводиться к поиску такой последовательности, которая после свертки с импульсной характеристикой канала имеет минимальное евклидово расстояние от зашумленной последовательности на входе приемника.
Пусть для марковской цепи с числом состояний L необходимо найти такие М последовательностей состояний, которые обладают максимальными вероятностями из всех возможных последовательностей и имеют в конечный момент времени tnv -е состояние.
Можно ввести следующие обозначения: log/P{S{0),S{l),...,S{n)}/— метрика последовательности S(0),S(1), ....,S(n) St (к)— обозначает г-е состояние Марковской цепи, i=0,...,L-l, в момент времени tk, Amv(k)= log/P{Si(k)\SJ(k-l)}/—M&rpnm перехода из у-го состояния цепи в г-е в момент времени tk, mut(k)= log/P{S (0), S(l), ..., St(k)}/— метрика последовательности состояний, которая в момент времени tk оканчивается в і-м состоянии и из всех последовательностей, оканчивающихся в тот же момент времени в том же состоянии, имеет и-ю по величине метрику (и=1,2,...,М). Из равенства (2.11) следует, что метрика последовательности состояний может быть записана в виде /97,98/: «;( )=\og[P{S{0)Ml-sm} = iog№(0)}]+ т=к т-к + log[P{5(m)i)S (m-l)}] = log[P{1S(0)}]+Amj(mM/„.,)( ) (2.12) Я)=1 w=l S“ (к) — вектор-решение размерности к+1, элементами которого являются состояния марковской цепи S(0), S(l),..., St (к) с метрикой т“ (к). Поскольку логарифм является монотонной функцией, более вероятная последовательность состояний будет иметь большую метрику. Таким образом, необходимо найти М последовательностей S(0), S(l), ..., Sv (п), которые будут иметь максимальные метрики.
Разработка алгоритма реализации многоуровневого алгоритма Витерби для протоколов v.32 И v.42
Современные системы телекоммуникаций без сомнений нельзя представить без использования корректирующих кодов, причем многие системы связи накладывают ограничения на длину помехоустойчивого кода, причиной которого является требованиями минимальных временных задержек передачи информации. Существует огромное многообразие кодов, однако существует достаточно ограниченное число коротких кодов, для которых полученые характеристики, приближенные к возможным теоретически, и созданы алгоритмы декодирования, которые могут быть реализованы на современном аппаратном обеспечении. На данный момент неизвестны аппаратные декодеры коротких блочных кодов, которые бы обладали вероятностными характеристиками декодирования согласно методу максималь правдоподобной оценки и не требовавшие перестроек при изменении соотношения сигнал/шум в канале. Предлагаемая архитектура декодеров приемлемой сложности для коротких блочных кодов соответствует выдвигаемым требованиям и будет инвариантной применительно к произвольным коротким линейным блочным кодам /15,20,25,46,51,72,93,100/.
Интерес к коротким кодам проявляется в приложениях, где требуются малые задержки в передаче информации, например в гибридной системе кодово-временного разделения каналов TD-CDMA. Это направление поддерживается в Европе комиссией ACTS (Advanced Communication Technologies and Services) в проекте FMA2, в Америке комитетом TR4.5 ассоциации производителей — TAI (Telecommunications Industry Association), а также другими развитыми странами. Большое внимание в развитии третьего поколения UMTS уделяется системам TD-CDMA с временным разделением дуплекса — TDD (Time Division Duplex). Актуальность применения коротких кодов в этих системах несомненна. Известно, что распределение задержек передачи данных на местных цифровых сетях, влияющих на глобальные сети, является важной проблемой. Увеличение длины корректирующего кода в определенных случаях приводит к увеличению задержки.
В настоящее время в системах с короткими кодами широко применяются свёрточные кодеки как с жестким, так и с мягким декодированием, построенные на основе свёрточных турбо-кодеков, и блочные кодеки с жестким декодированием. Свёрточные коды являются достаточно простыми с точки зрения их аппаратного декодирования. Но для вышеуказанных приложений свёрточные коды укорачиваются обрывом решетки кода (trellis termination), что приводит к значительному ухудшению их эффективности. Из коротких кодов наиболее эффективными являются линейные блочные коды.
На рис. 4.1 показано, что характеристики наилучших блочных кодов (коды Хэмминга, Голея, квадратично-вычетные и БЧХ-коды) находятся в пределах 0,5 дБ от нижней границы Шеннона (sphere-packing bound — SPB).
В аппаратной реализации представленные характеристики для коротких блочных кодов в настоящее время не достигнуты. Данные характеристики достижимы перечисленными ниже алгоритмами мягкого декодирования. В течение длительного времени изучались методы мягкого декодирования для блочных кодов, и, начиная с середины 60-х годов, разными учеными были предложены алгоритмы декодирования, использующие мягкое посимвольное решение в демодуляторе и позволяющие приблизиться к декодированию по максимуму правдоподобия (ML-декодированию или MLD) /15,20/.
Отметим основные недостатки этих алгоритмов: Приближение к ML-декодированию происходит только на больших отношениях сигнал/шум (алгоритм Чейза, алгоритм GMD (generalized minimal distance), обобщенный алгоритм Дейкстры — алгоритм А );
Используется арифметическое декодирование, зависящее от типа кода (алгоритм Чейза, алгоритм GMD). Данное обстоятельство не позволяет разработать универсальную архитектуру для декодирования различных кодов;
Высокая сложность декодирования для низких отношений сигнал/шум (алгоритм Чейза, алгоритм А ) приводит к неравномерной производительности таких декодеров в зависимости от состояния канала;
Алгоритм Витерби для блочных кодов использует решетчатое представление кодов при декодировании и рассматривает все узлы решетки кода, что экспоненциально увеличивает сложность декодирования при возрастании длины блока.
Избежать указанных недостатков позволяет декодирование с помощью упорядочивания принятых бит в соответствии с информацией об их надёжности и построения нового базиса на основании надежных символов с последующим генерированием множества тестовых кодовых слов, из которого выбирается результирующее. Объем множества тестовых слов определяет сложность алгоритма. На таком принципе построены алгоритм OSD (декодирование на основе порядковой статистики) и алгоритм мягкого перестановочного декодирования Дмитриева. Решающим аргументом в пользу выбора алгоритма Дмитриева для аппаратной реализации стал меньший объём его множества тестовых слов, что обуславливает высшую производительность алгоритма Дмитриева при сопоставимых с алгоритмом OSD-характеристиках. Для достижения характеристик ML-декодирования объём тестового множества алгоритма Дмитриева повышается линейно с ростом длины блока, в то время как для алгоритма OSD этот объём растет почти экспоненциалъно.
Структурная схема декодера на ПЛИС, реализующего модифицированный алгоритм Витерби
Составим многоуровневый алгоритм, реализующий декодирование Витерби. Блок-схема алгоритма представлена на рисунке 3.4. Рассмотрим подробнее алгоритм.
В первом блоке производится заполнение таблицы для верхнего и нижнего ребер, ведущих из j-ro узла решетки декодирования. Второй блок производит обнуление счетчика метрик, поскольку расчет еще не производился. Третий блок производит расчет метрики соответствия принятого ребра и эталонного. Начиная с четвертого блока начинается работа модуля «сложить-сравнить-выбрать». Вводится параметр а, равный накопленной сумме метрик при движении в узел по ребру.
Параметр Ь принимает значения накопленной суммы метрик при движении в узел по ребру. В пятом блоке происходит сравнение двух метрик, полученных при движении в узел 2 ]. В случае, если параметр меньше параметра, то в шестом блоке накопленная сумма метрик для узла 2 ] принимает значение параметра. Седьмой блок, в случае, если параметр больше параметра, то накопленная сумма метрик для узла 2] принимает значение параметра. Девятый блок реализует ввод параметра, равный накопленной сумме метрик при движении в узел по Параметр принимает значения накопленной суммы метрик при движении в узел по ребру. Десятый блок производит сравнение метрик, полученных при движении в узел 2] по ребрам 1. Одиннадцатый блок, если параметр меньше параметра, накопленная сумма метрик для узла 2j принимает значение параметра. Двенадцатый блок при условии, что параметр больше параметра, приравнивает накопленную сумму метрик для узла 2} к параметру. В четырнадцатом блоке происходит формирование пути по решетки декодирования путем соединения узлов с минимальным значением накопленной метрики. В пятнадцатом блоке происходит сравнение глубины декодирования и глубины задержки.
Семнадцатый блок проверяет все ли ребра декодированы. Если остались не декодированные ребра, то происходит следующая итерация /55,57,60/.
Основной вклад в вычислительные затраты вносят модули ССВ, на которые может быть разбита решетчатая диаграмма сверточного кода со скоростью 1/2. По очевидным причинам реализуемая этим модулем функция называется «сложить-сравнить-выбрать».
При оценке вычислительных затрат существенное значение имеет тип данных, используемый для хранения и обновления информационных путей А{(1) (1 = 0,1,... Е -1). Если для А1(1) в памяти ПЭВМ отводится байт или слово, то при обновлении информационных последовательностей с использованием операции присвоения типа AJ :=Aj(l) для всех значений /=0,1,... Е -1 требуется Е пересылок для данного узла. С другой стороны, можно увидеть, что реализация остальных операций в модуле ССВ требует произвести 8 простых арифметических операций с учетом индексирования. Поскольку глубина декодирования Е = 5000, то получается, что операция обновления информационной последовательности дает вклад в 4 раза больше, нежели, остальные операции.
Для хранения одного информационного символа достаточно использовать один бит. Если для Аі(1) в памяти ПЭВМ отводится 1 бит и выбирается Е=32, то для хранения элементов информационной последовательности требуется два слова для 16-ти разрядных и одно слово для 32-х разрядных ПЭВМ. В этом случае для обновления информационных последовательностей требуется лишь одна и две операции пересылки соответственно. Таким образом при использовании бита для реализации Ai(l) быстродействие модуля ССВ повышается, примерно, в четыре раза в сравнении с ситуацией, при котором информационному символу отводится один байт или слово ПЭВМ /119,120,121,122/.
