Декодер кодов рида-маллера порядка

(56) Авторское свидетельство СССМ 1474854, кл. И 03 М 13/00, 198Сагалович Ю.Л. Кодированиеи надежность автоматов. М.; Свс. 88-91, рис. 4,7;1.(54) ДЕКОДЕР КОДОВ РИДА-МАЛРЯДКАр ый инсуи, С,Н,Ли остояний зь, 1975,ЛЕРА П ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ВТОРСКОМУ СВИД(57) Изобретение относится к технике связи и вычислительной технике. Цель изобретения - упрощение декодера, Декодер содержит первый регистр 1, второй регистр 14, блок 8 декодирования кода нулевого порядка и узлы 2, 3 и 5 декодирования кода, в каждый из которых входят блок 15 алгебраического суммирования и блок 18.вычитания, В каждый из узлов 2, 3, 5 вводят блок 16 вычисления модулей и блок 17 ключей, а в каждый из узлов 4, 6 и 7 декодирования кода, аналогичных узлам 2, 3 и 5. вводят блоки 9 декодирования кода нулевого порядка, блоки 10-12 декодирования кода и блоки 13 перемножения. 2 з.п. ф-лы, 4 ил.Изобретение относится к технике связии вычислительной технике и может быть использовано в системах передачи дискретной информации,Цель изобретения - упрощение декоре.ра.На фиг,1 изображена блок-схема предлагаемого декодера кодов Рида-Маллера(РМ) третьего порядка, на фиг,2 и 3 - выполнение соответственно блока декодированиякода в-го порядка длины 2 и блока декодирования нулевого порядка длины 2"; нафиг,4 - пример конкретной реализации декодера кода РМ первого порядка длины 2 .зДекодер кода РМ содержит первый регистр 1, узел 2 декодирования кода г.-гопорядка длины 2, узлы 3 - 5, 6,1 и 6,2, 7.17,3 декодирования кода (г-)-го порядка(1= О,г - 1) длины 2= 1,а - г - 1) блока 8декодирования кода нулевого порядка длины 2" , блоки 9 декодирования кода нулевого порядка длины 2 " , блоки 10 - 12декодирования кода (г - 3)-го порядка длины2", блоки 13 перемножения и второй регистр 14,Каждый из узлов декодирования выполнен на блоке 15 алгебраического суммирования, блоке 16 вычисления модулей, блоке17 ключей и блоке 18 вычитания.На фиг.1 в скобках возле каждого узла2 - 7 или блока 8 - 12 указаны порядок кода ипоказатель степени двойки, характеризующий длину кода,Каждый иэ блоков 10 - 12 декодированиякода (г - )-го порядка длины 2"содержит г-определителей 19 знака.Каждый из блоков 8 - 9 декодированиякода нулевого порядка содержит сумматор20 и определитель 21 знака. Сумматор 20может быть реализован на двухвходовыхсумматорах 22, число которых на единицуменьше показателя степени двойки, характеризующего длину кода.Блоки 15 включают в себя сумматоры 23и вычитатели 24, Блоки 16 выполнены навычислителях 25 модуля (т.е, вычислителиабсолютной величины без учета знака), Блоки 18 выполнены на вычитателях 26. Блоки17 содержат ключи 27, Блоки 13 реализуются на перемножителях 28.Функционирование декодера основанона следующих принципах.,Пусть из линии связи получен искаженный вектор й/кода РМ порядка г и длины 2,Тогда обработка вектора Ю ведется вследующей последовательности,1. Если г = а, то декодируемые векторыУ и Т совпадают с вектором (Мцп(ЧЧ 1),9(ЧЧг), 3190(ЧЧп 2. Если г = О, то определяется знак велиичины , ЧЧ, который совпадает со знаком=1декодируемого символа У,2 = (У,У, У),3. Принятый вектор ЧЧ представляется ввиде матрицы ЧЧ размерности 2 х 2, содержащей две строки, в первой - элементы с нечетными, во второй - с четными номера4. Вычисляется матрица 5 = НгЧЧ размерности 2 х 2, где Нг - матрица Адамара1размерности два: Нг =15М5. Находится вектор Я размерности 2 1,равный разности модулей элементов первой и второй строк матрицы Я.6. Вектор 3 декодируется декодером ко 20 дэ(г)-го порядка длины 2 . Результатомявляется вектора У размерности К(г,г - 1е).= ", С; и ЕбВ(г - 1,щ) размерно=ости 27. Иэ матрицы Я выбираются элементы,образующие вектор Ю = (ЧЧ 1, ЧЧг, , ЧЧг)/ /размерности 2, причем ЧЧ равняется 1 му элементу первой строки 5, если Ъ) = 1 и1-му элементу второй строки, если Ъ ) -1,.(1)8, Вектор ЧЧ декодируется декодеромкода. г-го порядка длины 2 . Редльтатомдекодирования является вектор У г"размерностиСпи вектор Р) Е В(г,гп) раз 35 =Омерности 2"9. Результатом декодирования вектораЧЧ является вектор У = (У ),У(и вектор Е =40 2 гф,72 х 2 - ) размерности.2Поясняем это на примере кода РМ второго порядка длины 2 . Пусть в линию связибыл послан вектор:Ч= /1, - 1, - 1.1, 1, 1, 1, 1, -1, 1, 1, - 1; 1, 1, 1,45 1,1,1,1,1, - 1,1;1, - .1, - 1,-1, - 1, - 1, - 1,1,1, -1/,На приемной стороне принимается векторЧЧ = /1, - 1, - 1, 1, -1, 1, 1, 1, - 1, - 1, 1, -1, 1, 1.1,1,1,1,1,1,-1,1,1, - 1,1, - 1,-1, - 1, - 1,1,50 1, -1/ с ошибками на 5, 10 и 25 позициях.ф ( -1 1 11-1-11111 1-1-1 - 1 1 -) О 0 02-202222 000-2 0055 з=г-г-го огоооо-ггг о-гг )5 = ( - 2, -2, .-2, 2, 2, -2, 2, 2. 2, 2, - 2, - 2,- 2,2, -2, - 2),1660176 2. Вектор Я декодируется в узле декодирования кода РМ (1, 4), где 1 - порядок кода, 2 - длина кода.2.1гч(1.1), - 2 - 2 2 2 2 - 2 - 2 - 2 ) 5- 2 2 - 222 - 2 2 - 2- 4 0044 - 2 О - 4 0 - 4400 О - 4 0 10-4, 4, 4, 4, -4, 4), 8 ( 1.1 )Я = (4 -4 Ф "= (О, О, -8, О) 2,2. Вектор Я() декодируется в блоке декодирования кода РМ (О, 3)15: , У(1 1): (1, 1 1, 1 - , ,) 2.3. О/ =( - 4, О, О. 4,4, -4, 0,4) декодируетсяузлом декодирования кода РМ (1, 3)20( 04 - 4 - 4) 25 2.4. Вектор Р 2) декодируется блоком декодирования кода.РМ (О, 2)30=-1 Л =(-1,-1,-1,-1) 2.5. Вектор Ю =( - 4, -4,8,4)декодируется в узле декодирования кода РМ (1, 2) 35 4, Вектор ЧЧ = (4, 2, -2, 4, 4,-4, -2, -4)40 декодируется узлом декодирования кода РМ (2,3))ф ( 1 - 1 1 1 - 1 - 1 1 1 1 50 1, - 1, - 1, 1, 1, - 1, - 1)3. Вектор Я=(2, - 2, 0,2. 0,2,2,2,2,2,-2,2, О, - 2, - 2, 2) декодируется узлом декодирования кода РМ(2,4) 2 - 68 2 Я= (4 -4 -8 4),(з 1) ( 4 -8 55 1 4.1 ) ( 0 - 4 Я( 1) =( - 8 - 8). 8111)(. - 4 40 - 45= (О, 0 -8, 0) г(1 з) ( 48 ) (1 з) ( - 812 ) 2.6, Вектор Ю = (-8,12) декодируется блоком декодирования кода РМ (1, 1) щ у 20022-2 0 - 2 1, - 22222 2 - 2 2 0 2 244 0 - 2 0 4-2 - 200 - 4 2-4 Я= (-4, О, О. 4, 4, -4, О, -4),3.1, Вектор Я декодируется узлом декодирования кода РМ (1, 3) щ(г,1) ( - 40 4 0 )8(г,1) ( - 4 40 - 4 )- 4 - 48 4 3.2. Вектор 5) декодируется блоком декодирования кода РМ (0,2)(2,1) 1 Р 21) (1 1 1 1 3,3, Вектор Ю = ( - 4, -4, 8, 4) декодируетсяузлом декодирования кода РМ (1, 2)(гг) ( - 488(гг) ( - 812 )0;(г,г) (8 3 4 Вектор 5 декодируется блоком деко дирования кода РМ (0,1)У(22) 1 Р,г) (11)3.5. Вектор Ю = (-8, 12) декодируется блоком декодирования кода РМ (1,1)(2,3) ( 1 1) (2,3) ( 2 = (1, 1) 6 Д - 1, 1) = ( - 1, - 1. 1, 1) 7: 2) 6) Т = ( - 1, 1, -1, 1, 1, - 1, 1, - 1) 4.1; Вектор Гдекодируется узлом декодирования кода РМ (1,2)4,2, Вектор Бдекодируется блоком деко(3. 1)дирования кода РМ (0,1)4.3. Вектор Й/= (8. -12) декодируется блокомдекодирования кода РМ (1,1)у 3,2) (1 1)(3,2) (1 1)У") = 1 - 1, 1, - 1)Я 3,1) (3,2)5, Вектор Ю = (2, -6, 8, -6) декодируетсяблоком декодирования кода РМ (2,2)Ж ) = (-1, -1, 1, - 1) 2( ) = (1, - 1, 1, - 1)РезультатУ=(1, - 1, 1, - 1, 1, - 1, 1,-1, 1, - 1, 1, 1, 1,- 1, 1, - 1),Работает декодер следующим образом.Кодовый вектор длины 2 приходит иэ линии связи и записывается в регистр 1, откуда элементы вектора (зтомогут быть и действительные числа) подаются на вход блока 15 узла 2. Результаты суммирования и.вычитания подаются на входы блока 16 вычисления модулей узла 2. Полученные модули поступают на блок 18 вычитания узла 2, Результаты вычитания модулей поступают на узел 3 декодирования кода (г - 1)-го порядка длины 2, Результаты декодирования подаются на входы регистра 14. Блок7 ключей пропускает соответствующие числа с блока 15 на узел 4 декодирования кода порядка г длины 2 и т,д,Обозначаем С( )(г,гп), СР)(г,гп), С(3)(г,гп) С( )(г,гп) соответственно количество требуемых сумматоров или вычитателей, блоков определения модуля числа, блоков сравнения двух чисел, блоков смены знака на противоположный.Тогда для декодера кода РМ порядка г и длины 2 сложность можно определить системой рекуррентных соотношений:С( )(г,гп) = 3 2 + С( )(г,гп)++С( )(г, п 1-1)с краевыми условиямиС(п 1,п 1) = 0= 1,4; С )(О,гп) = О,Сгз) (О в)5 С( )(О,гп) = 0Решением системы являются соотношенияС(г,гп) (Зг+ 1) 2,10 Ср)(г,гп) = г 2", С(3)( ) С п - 1С(г,гп) = г 2,15из которых следует, что сложность декодерапропорциональна произведению длины кода на его порядок.Таким образом, предлагаемый декодер20 имеет сложность, пропорциональную пг)оизведению длины кода на его порядок, тогда как известный декодер имеет сложность,пропорциональную иоц"и, где и - длина кода25Формула изобретения1. Декодер кодов Рида-Маллера порядка г, содержащий первый регистр, вход ко торого является входом декодера, второйрегистр, выход которого является выходом декодера, узлы декодирования кода (г)-го порядка ( = Ох - 1) длины 2 (2 - длина исходного кода), каждый из которых включа ет в себя блок алгебраического суммирования и блок вычитания, и блок декодирования кода нулевого порядка длины 2 , выход кото рого соединен с первым входом второго регистра, выходы первого регистра подклю цены к входам блока алгебраического суммирования узла декодирования кода г-го порядка длины 2, выходы блока вычитания узла декодирования кода (г-К)-го порядка (К =- Ог:2) длины 2 "соединены с входами 45 блока алгебраического суммирования узладекодирования кода (г - К)-го порядка длины 2, выходы блока вючитания узла декодирования када первого порядка длины 2 " подключены к входам блока декоди рования кода нулевого порядка длины 2 ",о т л и ч а ю щ и й с я тем, что; с целью упрощения декодера, в каждый узел декодирования кода (г)-го порядка длины 2, введены блок ключей и блок. вычисления.55 модулей, выходы которого соединены с входами блока вычитания, выходы блока алгебраического суммирования подключены к соответствующим информационным входам блока ключей и входам блока вычисле 1660176 10ния модулей этого узла декодирования, кроме того, в декодер введены блоки декодирования кода нулевого порядка двины 2 и г б= 1,пг - г - 1), блоки декодирования кода (г - 1)-го порядка. длины 2", блоки перемножения и узлы декодирования кода (г - 1)-го порядка длины 2 "(и - 1 л - г), выполненные аналогично узлам декодирования кода (г - )-го порядка длины 2 выходы блока вычитания Ь-го (Ь = 1,Св+) узла декодирования кода первого порядка длины 2 " соединены с входами Ь-го блока декодирования кода нулевого порядка длины 2 "1, выходы блока ключей Ь-го узла деко 1 дирования кода (г - )-го порядка длины 2" подключены к входам Ь-го блока декодирования кода (г - 1)-го порядка длины 2 1, выходы блока ключей д-го (д = 1,С 1= О,а - 3: 1 = 0,1; для 1г- г) узла декодирования кода (г+т)-го порядка длины 2 соединены с входами блока алгебраического суммирования д-го узла декодирования кода (г - 1+1)-го порядка длины 2 , выходы блока вычитания д-го узла декодирования кода (г+1)-го порядка длины 2подключены к входам блока алгебраического суммирования (д +,), С) )-год =о узла декодирования кода (г -- 1о порядка 2, выходы первого - (С)-го Х)-целая часть Х) блоков деко 1 дирования кода первого порядка длины 2 соединены с первыми входами одноименных блоков перемножения и соответствующими входами выходного регистра, выходы блоков декодирования кода нулевого порядка длины 2 соединены с 0+1)-ми вхОдами одноименных блоков перемножения; управляющими входами блоков ключей одноименных узлов декодирования кода первого порядка длины 2 и соответствующими входами второго регистра, управляющий вход блока ключей узла декодирования первого порядка длины 2и (а-г)-й вход первого блока перемножения подключены к выходу блока декодирования кода нулевого порядка; длины 2" " 1, выходы первогов - г+К+1,Е( С и) - г + к + 1 . )-го блоков декодировар ния (г - К - 1)-го порядка длины 2 соединены с первыми входами соответственног - К - 11 УП-ГМГ- йЛ)1 К Сп,.в)го -ц .а Сгп.ву 5г 11-Г. ,Д вг)- -го блоков перемножения и соответствующими входами второго регистра. выходыи) - у 1-4первого - ( ;Я.)-го блоков перемно , -3 Цжения подключены к управляющим входам блоков ключей соответственно1 -1первого -(С)-з+ )-го узлов декоздированиякода второго порядка длины 2 , выходыв - г - 1 Г в а(1 + С)-з+ -го - ( , Сг-з+ )-го бло 1 -- 1ков перемножения соединены с.управляющими входами блоков ключейсоответственно первого - (Сп)-з " )-го уз 20 лов декоздирования кода второго порядкадлины 2 и вторыми входами соответственно (1 +, Сп)-ь)-го - (Сп)-з " ) +Ь=125 " -ЙФ+Сп) ь)-го блоков перемножения,Ь=1выходы которых подключены соответственно к управляющим входам блоков ключейпервого - (Сг+1 )-го узлов декодированиякода третьего порядка длины 2и т.д.,выходы последнего блока перемножения. соединены с управляющими входами блокаключей узла д 1 екодирования кода г-го порядка длины 2"+, выходы узла декодированиякода г-го порядка длины 2" подключены ксоответствующим входам выходного регистра.2.Декодер поп.1, отл и чаю щийсятем, что блок декодирования кода (г-)-гопорядка длины 2 содержит гопределителей знака, входы и выходы которых являются одноименными входами и выходамиблока,. З.Декодер по п.1, о тли ч а ю щ и й сятем, что блок декодирования кода нулевогопорядка длины 2содержит соединенные последовательно сумматор и определитель знака, входы сумматора и выход1660176 оставитель О,Ревинскийехред М,Моргентал Корректор С. Шевк Редактор Т.Горяче ГКНТ СССР Производс нно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина. 10 аказ 1855 Тираж 469 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям 113035, Москва, Ж, Раушская наб., 4/5