автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Топологическая организация БИС параллельных декодеров Витерби

САЯЮ'-ПЩЕРБУ^Ш ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ , *] ~ УНИВЕРСИТЕТ

На правах рукописи

АЛБМАХАИВ1 МУХАМЕЩ МАЗЕН ИВД

ТОПОЛОГИЧЕСКАЯ ОРГАНИЗАЦИЯ БИС ПАРАЛЛЕЛЬНЫХ ДЕКОДЕРОВ ВИТЕРБИ

Ойегпяальность: 05.13.05 - элементы н устройства вычислительной

техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 1993

л

Работа выполнена в Санкт-Петербургском государственном электротехническом университете.

Научный руководитель -кандидат технических наук допент ШУМИЛОВ Л.А.

Официальные оппоненты: ' доктор технических наук профессор ЯКОВЛЕВ В.В. кандидат технических наук СТАНКЕВИЧ Ю,А.

Ведущая организация - ЛОЭП "Светлана".

Защита диссертации состоится Об 1993 г,

в/^§ас. на заседании специализированного совета К 063.36.0' Санкт-Петербургского государственного электротехнического уш верситета по адресу: 157376, Санкт-Петербург, ул.Проф.Попова

С диссертацией можно ознакомиться в библиотеке универси'

та.

Автореферат разослан »¿Ц» (Ма/и 1993 г.

Ученый секретарь специализированного совета

Юрков Ю.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность Tgjij. Применение помехоустойчивого кодирова-1я является эффективнш методом улучшения энергетических ха-ютеристик систем связи.

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

Среди известных алгоритмов кодирования-декодирования свер-эчных кодов наилучшей корректирующей, способностью при прочих 1вных условиях обладают алгоритмы максимального правдоподо- " 1Я, а среда них - алгоритм Витерби, основанный на принципе ди-змического программирования.

Широкое применение алгоритма декодирования Витерби сдеряи-злось до настоящего времени большими аппаратными затратами, эобходимыми для его реализации. Кардинальным решением этой эоблемы является разработка специализированной элементной базы т сиетей помехоустойчивого кодирования, ориентированных на рот алгоритм и его модификации. Актуальность проблемы подтвер-jaerc'av ® частности, интенсивной разработкой БИС декодеров Ви-зрб^г йедущи^ зарубежными•электронными фирмами, аннонскровавши-v V последнее время,ряд новых разработок в этой области. Обра-letf На; себя внимание, что БИС декодеров Витерби - это очень тожнйе' cieftfa с размером кристалла 10*10 мм и выше, реализуемые з самым совершенным КЮП технологаям с 1,0 ... 1,5 микронными эпологические нормами.

^лтература в области декодеров Витерби весьма обширна, од-1ко носит в основном теоретический характер и посвящена инфор-шионным основам алгоритмов кодирования-декодирования. Практи-зски отсутствуют работы, посвященные вопросам технической реа-1зации декодеров Витерби и в особенности вопросам реализации в 1де SIC на базе современных микроэлектронных технологий.

Объектом^сслецования в настоящей работе являются парал-эльные декодеры Витерби, в которых обработка информации выпол-т^тся р ремлЫ1 ом масштабе времени, а для согласования со ско-

N

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

Цель_]эабдты - анализ структурно-функциональных особенное тей параллельных декодеров Витерби и разработка экономичных п затратам площади кристалла топологических реализаций декодера

У§12Щ_Я£следования - аппарат теории помехоустойчивого к дирования, теории проектирования больших интегральных схем, приемы и методы схемотехники и топологии КМОП ШС.

ОсНовные_£§з^льтаты_Еаботы:

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

2. Разработаны схемные и топологические решения узлов де кодера Витерби, поддерживающие в форме библиотеки функциональ ных фрагментов процесс проектирования КМОП ШС декодера.

Вн§щение_результатовработы. Основные результаты работы использованы при выполнении научно-исследовательских работ в ЛОНИИР.

Апробация_работы. Основные положения диссертационной раб ты докладывались и обсуждались на научно-практической конфере ции профессорско-преподавательского состава ЛЭТИ им.В.И.Ульян ва (Ленина) в 1990 г. и на Международном симпозиуме "Спутнике вая связь: реальность и перспективы" (г.Одесса, 1990 г.).

Публикации. По материалам диссертации опубликованы 2 печатные работы.

Стр2!?гД;а_и_объем_£аботь1. Работа содержит введение, три главы, заключение, список литературы, включающий 30 наименова ний. Основная часть работы изложена на 129 страницах машнопи ного текста. Работа содержит 56 рисунков и 3 таблицы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во_вводен7и показана актуальность темь: диссертации, сфо^ мулированы цель и задачи исследования, дана общая характерист ка работы.

0^22.-2_глава носит обзорный характер и посвящена фиксаци используемых в работе определений, терминов и понятий, связан ных со сверточкыми кодами и алгоритмом Витерби.

Задачу декодирования сверточных кодов (СК) можно рассмат-гаать как задачу нахождения пути на решетчатой диаграмме с по-щыо определенных правил декодирования. Предложенный Витерби 1горитм реализует метод максимального правдоподобия для двоич-« симметричных, каналов с независимыми ошибками. Декодер Витер-г (ДКВ) для любой принятой кодовой последовательности /< ♦ У*»• • • выбирает информационную последователь-

ють (путь на решетчатой диаграмме) таким образом, чтобы соот-гтетвующая ей кодовая последовательность , ,..., яг4-,.., наименьшей степени отличалась от принятой. В случае жестких зшений, когда на вход декодера поступают двоичные символы, в шестве меры близости между двумя кодовыми последовательностя-I {хЗ и {у} обычно используют расстояние Хемминга. При этом гкодер максимального правдоподобия обеспечивает такой выбор * 1формационной последовательности, при котором двоичные кодовые зследовательности {х} и {у} имеют минимально возможное число сличающихся символов л* л у- .

Решетчатая диаграмма ДКВ имеет число состояний М - 2 , 1е 9 - длина кодового ограничения. Для кодовой скорости « 1/2 диаграмма имеет следующие свойства:

1) из каяздого узла, характеризующегося состоянием у , ис-» здят два ребра. Одно из них, соответствующее нулевому информа-юнному символу, ведет в состояние (2</ )тос[ М , а другое - в ютояние + I) тас1 Ы.. Последнему соответствует единичный 1формаиионный символ:

2) в каждый узел, имеющий состояние у , идут два ребра. ;но из них исходит из узла Гу £>] , а другое - из узла с зстоянием / 20 .

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

Предположим, что путь с наименьшей метрикой заканчивается злом в состоянии / . Задача состоит в том, чтобы на основе ■годной информации (принятых символов кодовой последовательнос-0 найти наилучший путь на следующем уровне узлов. Проведем

ч

произвольно /V — I путей (ррвных по длине наилучшему) таким о! разом, чтобы они заканчивались в различных узлах, исключая уж! занятый узел в состоянии у . Если наилучший путь имеет метри) т^ , то для остальных путей

/п1 Ъпу » = I ••• N » '•

Выберем на следующем уровне узлов на решетчатой диаграмм некоторый узел с состоянием р , В него согласно сформулирова ным выше свойствам диаграммы ведут два ребра из состояний ¿> «= Ср/2.1 и = /Ч/' + Л')/2 7. Сопоставляя соответствуют этим ребрам кодовые символы с принятыми символами, можно вычи лить приращения метрик лгггц и лтц вдоль указанных ребер. В результате в состояние р ведут два пут;и. Один - с метрикой

- + ¿/77<> , а другой - с метрикой г*У/>г ш /77«'г +&гттсг Путь с наибольшей метрикой может быть изъят из дальнейшего ра смотрения. В итоге выживает путь с наименьшей метрикой как на более правдоподобный. К информационной последовательно :ти дол бить-добавлен нулевой символ, если р - четно, и единичный -противном случае. Последнее непосредственно следует из первог свойства решетчатой*диаграммы.

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

Все У выживших путей, как правило, различаются лишь на конечных участках и на определенной глубине сливаются друг с другом. Глубина, на которой происходит слияние, не может был вычислена заранее; она является случайной величиной, зависят« от ошибок в принятой кодовой последовательности. Поэтому при практической реализации декодера устанавливают фиксированную глубину декодирования А , на которой пути сливаются с достаточно высокой вероятностью. Обычно глубину Ь выбирают равн< (6...7) 1? .

Каждый раз, когда к путям присоединяется новое ребро, а мые старые информационные символы поступают на выход для при тия окончательного решения. Если выжившие пути на глубине сЛ1 ваются, то все М выходных символов совпадают, что дапт возм

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

В качестве меры эффективности помехоустойчивых кодов часто пользуют величину энергетического выигрыша от кодирования >ВК), равную значению дроби, в числителе которой - отношение гнал/шум системы с помехоустойчивым кодированием, а в знамв-теле - отношение сигнал/ шум для простой системы с безызбы-чным кодированием. В общем случае ЭВК декодера Витерби завит от длины.кодового ограничения ^ , скорости кода Я , числа овней квантования входного сигнала О, и длины памяти декодера . Типичными экспериментальными значениями являются [13 : К ='4,9 дБ при Я = 1/2, Ь = 32, О. = б и вероятности ошибки = 10' . Переход от.жестких решений к В- уровневому квантована дает прирост ЭВК порядка 2 дБ. Увеличению ^ на единицу путствует увеличение ЭВК на 0,3 ... 0,4 дБ, однако экспонен-альный рост сложности ДКВ ограничивает 7 значениями порядка ..В.

Одно из неоспорймых достоинств алгоритма декодирования Ви-рби - легкость использования мягких решений. Другим его досто-ством является простота декодирования кодов с Я>1/2, если и получены из кода с = 1/2 методом выкалывания (удаления кодовой последовательности) отдельных кодовых символов. Та-е коды называют перфорированными.

Для декодирования перфорированных кодов достаточно усло-ться, что метрика стертых символов равна нулю. Перфорированные ды имеют почти такие же характеристики, что и наилучшие изве-ные коды с /? > 1/2, поэтому они широко используются на практи-. Однородность декодирования перфорированных и неперфорирован-х сверточных кодов дает возможность создания универсального кодера Витерби, работающих при нескольких значениях кодовой

ч

скорости R .

Структура ДКВ логично вытекает из анализа алгоритма дек< дирования и может быть разделена на три части: вычислитель м< рик ветвей (ВМВ), блок сложения-сравнения-выбора (ССЗ) и паи выживших путей (ПВП).

рассматриваются принципы построения, opi низаши и функционирования всего ДКВ в целом и перечисленных его частей - ВМВ, ССВ и ПВП.

На структурном уровне свойства схемы ДКВ могут быть огон ны 6-ю переменными: длиной кодового ограничения - & , скоростью кода - R а & /п. (две переменные), разрядностью метр! ветвей - т , разрядностью блока ССВ.- ^ , числом уровней квантования на выходе демодулятора - Q, .

Блок ВМВ является входным блоком ДКВ, он преобразует^ £ogtQразрядных двоичных потоков с выхода демодулятора в 2 ffl -разрядных потоков. Поскольку обычно ограничиваются кванто] нием на восемь уровней» используя практически полностью возм! ности мягкого декодирования, то блок ВМВ реализуется с Q = I

Теоретически метрика ветви должна быть пропорциональна ; лобной вероятности передачи символов, соответствующих этой в ви при условии заданного набора принятых решений демодулятор; На практике применяют метод линейного сопоставления метрик, i котором метрика ветви является суммой метрик, соответствующи: каждому принятому символу; при этом ее максимальное значение равно 14, и для представления требуется л» = 4. Для сокращен числа разрядов предложен [Z1 метод неоптимального сопоставле метрики, позволяющий уменьшить максимальное значение до 7-ми ограничиться /»7=3. Ухудшение эффективности декодирования, п этом крайне незначительно и не превышает 0,1 дБ.

В работе для R = 1/2 приводится схеглное решение, треб щее на каждую ветвь одного двухразрядного сумматора и 5-ти с 2И. Преобразование, выполняемое блоком ВМВ, носит чисто комб напионный характер и не ограничивает быстродействия ДКВ. Ann ратные затраты на ВМВ удваиваются при увеличении п. на един

В блоке ССВ реализуются следующие операции:

1) сложение метрик предшествующих состояний с метриками соответствующих ветвей;

2) сравнение метрик путей, входящих в каждое состояние;

метрики путей получаются в результате первой операции;

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

Дня выполнения указанных операций на каждое из 2 состояний решетчатой диаграммы в блоке ССВ параллельного ДКВ должен быть предусмотрен процессорный элемент (ПЭ), содержащий два сумматора, компаратор и регистр. Информация в ССВ обрабатывается по рекурсивной процедуре, в связи с этим быстродействие ССВ определяет максимальную скорость передачи информации через ДКВ. Связи между ПЭ определяются решетчатой диаграммой, и сложность блока ССВ возрастает более чем в два раза при увеличении.3 на I. Таким образом для увеличения ЭВК примерно на 0,4 дБ при вероятности ошибки на бит ^ = 10 приходится более чем вдвое увеличивать сложность блока ССВ.

При выборе Ц- (разрядности блока ССВ) руководствуются следующими соображениями. Можно считать, что наилучший путь имеет нулевую метрику, а любой другой путь на глубине диаграммы состояний должен слиться с. наилучшим не позднее чем через Р шагов. Тогда, например, для кода й = 1/2 максимальное значение не превысит до момента слияния путей, в частности, при

у = б и Шц = 7 максимальное значение метрики пути равно 42 и поэтому = 6.

Более радикальным средством сокращения разрядности метрики пути является принудительное ограничение их величины [21 . Например, если в процессе вычисления должно сформироваться значение метрики больше 15-ти, то она устанавливается равной 15 (в этом случае достаточно = 4). Казалось бы, что столь резкое уменьшение диапазона значений метрик должно существенно сказаться на эффективности декодирования. На самом деле это не так, потому что путь с большим значением метрики почти наверняка не может быть истинным; большое значение метрики может возникнуть лишь в результате нескольких маловероятных ошибок. В результате ухудшение эффективности, связанное с ограничением максимального значения метрик пути величиной 15, составляет всего 0,2 дБ.

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

л

действительности при воздействшпомех метрика постепенно нарастает, и если не принять специальных мер, все метрики выйдут за пределы разрядной сетки. Для предотвращения переполнения производят так называемое нормирование метрик, когда их значения одновременно уменьшают на одну и ту же величину . С этой целью в состав блока ССВ включен узел нормировки. В принципе величина ты может быть любой, однако имеются некоторые соображения, позволяющие сделать обоснованный выбор. Если величина тн мала, операция нормировки будет осуществляться довольно часто. При этом уменьшаются различия между режимом нормальной работы и режимом рассинхронизаши. С этой точки зрения следует увеличивать тн . С другой стороны, большие значения порога нормировки увеличивают значение метрик, что в свою очередь увеличивает число двоичных разрядов, требуемых для 'их представления. С учетом этих двух обстоятельств для варианта ВМВ с. т = 3 и ограничением максимального значения метрики пути на уровне & можно определить в качестве величины порога нормирования значение в. Тогда узел нормировки контролирует старший разряд одновременно всех компараторов ячеек ССВ.

ПВП является выходным блоком параллельного ДКВ. Ее можно представить в виде Ь разрядных сечений по 2 . ячбек. Каждая ячейка имеет достаточно простую схему, состоящую из триггера с мультиплексором на выходе, поэтому быстродействие ПВП не ограничивает общего быстродействия ДКВ. Аппаратные затраты на блок ПВП возрастают более чем в два раза при увеличении 9 на -единицу.

Основное содержание третьей_главы работы посвящено вопросам планирования топологии блоков ДКВ, прежде всего ССВ и ПВП, как наиболее сложных по характеру связей между функциональными элементами. Рассмотрено также обоснование принятых решений по схемотехнике и топологической реализации функциональных элементов.

Связи между ПЭ в блоке ССВ можно разделить на две группы:

а) глобальные связи, которые должны быть подведены ко всем ПЭ; их объем не зависит от информационных характеристик ДКВ; это - шины метрик ветвей, шины синхронизации и выходные шины;

б) локальные связи, по которым ПЭ обмениваются метриками путей. В общем случае их число равно 2 , и они имеют весьма

ж

замысловатый характер.

Локальные связи ССВ можно интерпретировать дугами направленного графа де Брейна, имеющего 2 вершин, причем каждая содержит две,,входящих и двег исходящих дуги. Для графа де Брейна существует хотя бы один гамильтонов цикл, т.е. путь обхода всех вершин таким образом, чтобы любая из вершин встречалась бы один раз. Располагал ПЭ так, чтобы их номера образовывали бы гамильтонов цикл, схему ССВ можно преобразовать в кольиевую структуру, где ПЭ соприкасаются входными и выходными гранями, благодаря чему затраты трассировочного пространства на локальные связи сокращаются примерно в два раза.

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

Топология самих сдвоенных ПЭ организована по принципу разрядных сечений. В верхней части разрядного сечения размещены два двоичных сумматора, имеющие зеркально-отраженную взаимную ориентацию. Учитывая крайне высокую общую сложность блока ССВ при выборе схемотехники сумматоров предпочтение было отдано наиболее апробированному, часто применяемому в зарубежной и отечественной технике комплементарному статическому варианту на 24-х транзисторах. На выходах сумматоров в соответствии с функциональной схемой ПЭ стоят мультиплексоры "2 в I", управляемые сигналом переноса из старшего разряда соответствующего сумматора ПЭ. Для их реализации были использованы проходные транзисторы, позволяющие выполнить экономичное объединение схем сумматора и мультиплексора.

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

С целью унификации топологических фрагментов, покрывающих поле разрядного сечения ПЭ, операция сравнения заменена операцией вычитания'в дополнительном коде, и для управления мультиплексором использован сигнал переноса из старшего разряда сум-

\

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

При разработке топологии в настоящей работе применен сеточный символический метод проектирования с топологическим стилем "сдвоенная диффузионная линейка" СзЗ.

ПВП декодера Витерби функционально можно представить в виде последовательности из ¡л разрядных сечений, содержащих по 2 в степени ^ ячеек ПВП, каждая из которых состоит.из триггера с мультиплексором "2 в 1" на входе. Топологически все проблемы реализации ПВП в основном заключаются в выполнении связей между разрядными сечениями. Связи могут быть классифицированы на глобальные - символьные шины, шины земли, питания и синхронизации, а также локальные - связи между выходами триггеров предыдущего разрядного сечения и входами мультиплексоров последующего разрядного сечения. Реализация глобальных связей очевидна: они могут проводиться сквозными трассами, и их конфигурация не зависит от информационных параметров ПВП. Напротив, локальные связи весьма сложны.. Одной из причин этого является необходимость связывать выход каждой ячейки одного разрядного сечения со входами двух ячеек соседнего сечения. Возникает естественное желание локализовать эту особенность, что можно осуществить, например, на базе следующей идеи двухэтапной трассировки: на первом подготовительном этапе выходы ячеек ПВП переставляется некоторым подходящим образом так, чтобы на втором завершающем этапе производилось размножение выходов и необходимое подсоединение их ко входам ячеек принимающего разрядного сечения. Было бы очень хорошо, если бы удвоенные связи второго этапа локализовались между одноименными ячейками принимающего и преобразованного передающего разрядного сечения.

Подходящее размещение ячеек в преобразованном передающем разрядном сечении удалось найти в виде следующего правила: двоичные номера ячеек в нем должны "быть образован^! из номеров ячеек непреобразованно1о сечения с помощью операции циклического сдвига вправо.

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

Соседней перестановкой, по определению, будем называть перекрестную связь между входами и выходами соседних элементов, при которой:

выход -го элемента соединяется со входом (С + 1)-го,

выход (4 + 1)-го элемента соединяется со входом I -го. После прямой передачи, когда выход I -го элемента соединяется со входом ь -го - это простейший для технической реализании вид связей между разрядными сечениями. Удобство соседних перестановок состоит в том, что множество их может быть осуществлено в едином трассировочном канале. Было бы заманчивым представить первый этап трассировки в виде нескольких шагов, но на каждом из них делать только соседние перестановки. Такая возможность была обнаружена. Ключ к решению задачи оказался в том, чтобы, двигаясь от центральных элементов, на кавдом шаге совершать число соседних перестановок, равное номеру шага. Всего требуется (2 - I) шагов перестановок, причем на последнем таге участвуют все элементы, кроме двух крайних.

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

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

Выполнение соседних перестановок с помощью соответствующего рисунка выходных трасс разрядных сечений и полное выполнение перестановок в виде ортогональных перемещений за (2 - I) промежуточных тактов между основными информационными тактами ДКВ можно рассматривать как два крайних технических- решения. Оптимальное решение лежит меэвду ними, когда частично перестановки выполняются трассировкой, а частично - в виде парного обмена между триггерами.'

При сценке замедления работы ДКВ за счет введения-промежу-

\

точных пактов необходимо учитывать, что узким местом по быстродействию, является блок ССВ, ибо логическая глубина схем вПВЛ значительно меньше, чем в ССВ. Метод ортогональных перемещений, таким образом, можно рассматривать как способ согласование скорости относительно медленного ССВ с более быстрой, ПВП с получением выигрыша в площади кристалла за счет упрощения связей между разрядными сечениями ПВП. В делом, применение этого метода дает возможность реализации параллельного ДОЗ для •О « 6 на одном кристалле при двухмикронных топологических нормах в КМОП процессе с двухслойной металлизацией.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Выполнено обоснование"экономичной компоновочной структуры для.блока сложения-сравнения-выбора ДКВ на базе выделения гамильтонова цикла в графе связей между процессорными элементами блока. ^г

2. Предложен способ двухэтапной трассировки связей мевду ячейками памяти выжившх путей ДКВ, по которому на первом этап« выполняется перестановка выходов ячеек, а размножение выходов I парные перекрестные соединения - на втором.

3. Перестановки выходов первого этапа трассировки описаны с помощью комбинаторной операции "обратной.тасовки". Предложен способ выполнения обратной тасовки в виде многошаговой процедуры соседних перестановок.

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

ЛИТЕРАТУРА

I. tie£êo9 ¿(Л., ¿facoSs Z.M. MU*/,-

лее с upww"-

2. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи / Пер. с англ. - М.: Радио и связь, 1987. - 392с.

3. West МИ.Е., £зАча.о/иап.. /С. „ Ръпе/p^ej с^ CMOS VLSI #e&e//Wa Sfas., ¿7c/c/,se>n. -ууа€ер, <9 М- "

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРГАЩИ

1. Мазен A.M., Шумилов Л.А. Кольцевая структура блока сложения-сравнения-выбора декодера Витерби / Санкт-Петербургск. гос. электротехн. .ун-т. С.-Пб., 1993. - 11с. - Деп. в ВИНИТИ. 30.03.93, » 775-В93.

2. Мазен A.M., Шумилов Л.А. Двухэтапная трассировка связей в памяти выживших путей декодере- Витерби / Санкт-Петер-бургск. гос. электротехн. ун-т. - С,- Пб., 1993. - 9с. - Деп. в ВИНИТИ. 30.03.93, № 776-В93.

Подл, к печ. 17.05.93. Формат 60 х 84 I/I6

Офсетная печать Печ. л. 1,0: уч. - изд. л. 1,0. Тираж 100 экз. Зак.№ 97. Бесплатно

Ротаппинт С.-Пб.ГЭГУ 197376, Санкт-Петербург, ул.Ироф.Попова, 5