Устройство для декодирования с коррекцией ошибок

(51) 4 Н ОЭ И 13/О ОПИСАНИЕ ИЗОБРЕТЕ ти- кой На фиг. 1 привества для декодировошибок; на фиг, 2контрольных разрядрупненный алгоритмустройства на фиг к вычисли- пользоватьобработки ена схе ния с к формир а устро ррекцие ватель г, Э- ировани й функцио йст странс ГОСУДАРСТЗЕННЫЙ КОМИТЕТГЮ ИЗОБРЕТЕНИЯМ И (ЛНРЬОИОРИ ГННТ СССР И АВТОРСКОМУ СИИ(71) Киевский политехнический инстут им. 50-летия Великой Октябрьссоциалистической революции(54) (57) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯС КОРРЕКЦИЕЙ ОШИБОК, содержащее первый регистр, выходы которого подключены к первым входам первого сумматора и информационным входам второгорегистра, выходы которого подключенык первым входам второго сумматора иинформационным входам третьего регистра, первые и вторые выходы которого соединены соответственно с входами формирователя контрольных разрядов и первыми входами блока сумматоров, блок деления и блок элементовИ, выхода которого соединены с вторьки входами блока сумматоров, выходы которого являются выходами устрой Изобретение относитсятельной технике и макет исся в системах передачи ицифровой информации.Цель изобретения - упрощение ства, первые и вторые выходы формирователя контрольных разрядов подключены к вторым входам соответствующих сумматоров, выходы которых соединены с соответствующими входами блока деления, информационные входы первого регистра являются информационнымивходами устройства, тактовые входы .регистров объединены и являются так" товым входом устройства, о т л и " ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введены четвертый регистр, первый и второй счетчики импульсов и элемент И, выход которого соединен с управляющим входом второго счетчика импульсов и так- аФ товым входом четвертого регистра, инФормационные входы которого лодкыеве" Я ны к выходам первого сумматора, выходы блока деления соединены с установочными входами второго счетчика импульсов, выхода которого и выходы четвертого регистра подкювочены соответственно к первым и вторым входам блока эле-заев ментов И, выходы первого счетчика им" фь пульсов соединены с первыми входами ф элемента И, второй вход которого обь- р единен со счетнычи входами счетчиков р импульсов и подключен к тактовомувходу устройства.Ю1446695 000000000 000000000 101111111 000001111 000110011 011010101 Н = 011234567 венно-временная диаграмма работы уст.ройства.Устройство для декодирования с коррекцией ошибок содержит первый -5 четвертый регистры 1-4, формирователь 5 контрольных разрядов, первый 6 и второй 7 сумматоры, блок 8 деления, первый 9 и второй 10 счетчики импульсов, блок 11 элементов И, эле мент И 12 и блок 13 сумматоров. Кроме того, на фиг. 1 обозначены информационные 14 и тактовые 15 входы и выходы 16.Регистры 1, 2 и 4 - параллельные 15 в-разрядные, где ш - разрядность кодового символа в декодируемом коде.Регистр 3 представляет собой кразрядный регистр сдвига, где к - число информационных символов в кодо вом слове, причем каждый его разряд представляет собой параллельный регистр, аналогичный регистру 1.формирователь 5 контрольных разрядов выполнен в соответствии с кон кретно используемым кодом. Для систематического кода с основанием ц=2 и проверенной матрицей размера гхп=2 х 9; г=пс, п=1 с+2=2 +1,каждую кодовую комбинацию которого представляют кодовым вектором Х (р,р хх,х,х 4 хх,х,), где р, - .первая группа контрольных разрядов р - вторая группа контрольных раэрядов 1 х . - ь-я группа разрядов данных, про 40 верочные элементы вычисляют на основании общего матричного уравнения НхН = 0 в соответствии с равенствами5 Р = Х +Х+Х+Х 4+Х +Х,+Х 1р 4 = х,+2 х+Зхз+4 х 4+5 х,+бх,+7 х где в = 3; и = 9; 1 с = 7; О " нуле 50 вой вектор-столбец,При этом операции над элементами матрицы р, и х . выполняют как над элементами конечного поля СР(ц) порядка с 1 = 2 = 8, представляя каждый из них в виде полинома не вьппе второй степени, либо группой Ъвоичньх коэффициентов этого поли- нома, либо его восьмеричным номером. В предлагаемом устройстве хранение,передачу от блока к блоку и обработку этих элементов осуществляют именФ но в виде (а=3)-разрядных групп двоичных коэффициентов. При этом матрицу Н можно в двоичной форме представить следующим образом: В соответствии с выражениями для р и р в приведенном примере формирователь 5 контрольных разрядов (фиг. 2) содержит первый канал суммирования группы разрядов данных на сумматорах 17, второй канал суммирования взвешенных групп разрядов данных (каждая из которых умножена на свой коэффициент-константу) на сумматорах 18 и шесть -блоков 19-24 умножения на константы от 2 до 7.Сумматоры 6 и 7 и блок 13 сумматоров производят суммирование по модулю два.Блок 8 деления может быть реализован на постоянном запоминающем устройстве (ПЗУ), в котором записана соответствующая таблица деления элементов конечного поля СР(о) порядка ц=2Счетчики 9 и 1 О имеют емкость и = =1 с+ 2=2 +1,Сумматоры 17 и 18 (фиг, 2) осуществляют суммирование по модулю два.Блоки 19-24 умножения на соответствующую константу осуществляют умножение элемента конечного поля на константу и могут быть реализованы на ПЗУ либо в виде дешифратора с шифратором, либо ка логических элементах путем синтеза методом диаграмм Вейча. Так, например, блок 22 умножения на константу 5 имеет следующую таблицу истинности (в двоичном представлении): Синтез методом диаграмм Вейча даБулевы выражения для выходных раэ446695 5рядов блока 22:= у у +у уоггУо г УгРабота устройства основана на выполнении алгоритма декодирования с5коррекцией ошибки, Укрупненно этоталгоритм представляют в виде следующей процедуры (фиг, 3):1, Формируют в декодере две группы Р и Рг контРольных РазРЯДов из 10к информационных групп разрядов х;,содержащихся в регистре 3.2, Сравнивают одноименные группыконтрольных разрядов р и р с выхогдов формирователя 5 контрольных разрядов и р и р с выходов регистров11 и 2 посредством сумматоров 6 и 7и получают две группы разрядов проверочного синдрома Б, и Я г для данной кодовой комбинации. При этом, если в одной из 1-в-разрядных группрегистра 3 произошла любая ошибка,то первая группа разрядов Б синдро 1ма представляет со бой величину ошибки 6, а вторая Я г - произведение 25величины ошибки г, на номер Ь искаженной позиции в кодовой комбинации.При этом речь не идет о возможнойлюбой ошибке в первой или второйгруппе контрольных разрядов, поскольку получатель данных отбирает из декодера только к групп разрядов данных и полностью игнорирует контрольные разряды. Поэтому корректироватьошибку в первой или второй группе35контрольных разрядов необязательно.3, Делят величину Б , представленную второй группой разрядов синдрома, на величину ошибки е = Я и оп 1ределяют номер Ь искаженной позиции 40(группы разрядов),4, Корректируют искаженную группуразрядов х отыскивая ее по найденному порядковому номеру Ь и прибавляя к ней величину е ошибки в блоке 4513 сумматоров. При этом получают истинное значение Ь-й группы данных хцфтг 1которая, была искажена. Каждый элементкодовой комбинации (как информационный, так и контрольный) формируют в 50виде группы, содержащей в двоичных.разрядов, и ставят в соответствие одному из элементов конечного поля поРядка 1=2 ф,На диаграмме работы устройства(фиг, 4) обозначено; а - тактовые импульсы; б - состояние первого счетчика; в, г - состояние первого 1 и второго 2 регистров; д-л - состояния раз" 6рядов третьего регистра 3, м - импульсы на выходе элемента И 12, н моменты записи величины ошибки в четвертый регистр 4;. о - момент коррекции ошибок в блоке 13, и - состояния второго счетчика 10; р . - очередность появления данных на выходах 16.Устройство работает следующим образом.В исходном состоянии первый счетчик 9 обнулен, состояния регистров 1-3 и второго счетчика 10 произвольные.Пусть для примера в=З, тогда п=9. На входы 14 устройства поочередно подают п=2 +1=9 групп в=З двоичных разрядов, сначала информационные, затем вторую и первую группы контрольных разрядов. Под действием тактовых им" пульсов, например, по заднему их фронту (фиг. 4 а) в регистрах 1-3 эти группы сдвигают п=9 в течение п=9 тактов, причем к=п=7 информационных групп помещают в регистр 3. Процесс продвижения информации в ячейках регистров 1-3 иллюстрирован на фиг.4 в-л. Ячейкам регистра 3, как и (в=З)-. разрядным двоичным группам данных, помещаемым в них, присваивают порядковые номера , начиная с первой ячейки регистра 3 от г.=1 до г.=1=7. В. данном примере это порядковые номера 0,1,2,3,4,5,6,7 (на фиг. 2 это блоки х; для г. = 1,,7). По окончании (п=9)-го тактового импульса в регистре 3 оказываются все к=7 информационных (в=З)-разрядных групп данной кодовой .омбинации, которые подают на входы формирователя 5 контрольных разрядов.Две группы контрольных разрядов р и р , сформированные, как описано выше, подают на первые входы сумматоров 6 и 7, где их суммируют с соответствующими группами контрольных разрядов р и р из регистров 1 и 2. Если в какой-либо из к=7 групп разрядов данных регистра 3 произошла любая ошибка, то после окончания (и 9)- го тактового импульса значения (в=З)- разрядных элементов синдрома на выходах сумматоров 6 и 7 будут отличны от О. При этом значения разрядов Б, на выходе сумматора 6 показывают величину ошибки е,а значения разрядов Я на выходе сумматора 7 показывают произведение величины ошибки е на номер искаженной позиции Ь. Посредством бло 1446695ка 8 деления определяют номер искаженной позиции, выполняя операцию деления величины, представленной ш разрядами Я, с выхода сумматора 7, на вевеличину ошибки е с выхода сумматора 6. Задним фронтом 9-го тактового импульса первый счетчик 9 устанавливают в нулевое состояние (фиг. 4 б). Его выходные сигналы при этом отпирают 10 элемент И 12 и разрешают тем самым очередному тактовому импульсу (фиг4 м) осуществить установку разрядов второго счетчика 10 и регистра 4 в соответствии с поступившими на их 15 информационные входы сигналами. В этот тактовый период на входах регистра 4 присутствуют сигналы, представляющие в двоичной форме величину ошибки е, а на входах второго 20 счетчика 10 - сигналы, представляющие номер искаженной позиции в регистре . 3 (число 1,27), либо в регистре 1 (число 0) в соответствии с элементами второй строки матрицы Н (фиг.4 н),25 Пусть ошибка произошла на седьмой позиции в первой кодовой комбинации. На фиг. 4 в-л показано продвижение искаженного элемента 7. 1 в сотаве пер вой кодовой комбинации, По окончании девятого такта первый счетчик 9 устанавливают в состояние "О" (фиг,4 б) и очередним тактовым импульсом (фиг.4 м) записывают в регистр 4 величину ошибки, а в счетчик 10 номер 7 (фиг.4 н). Выходними сигналами счетчика 10 в состоянии к=7 отпирают блок 11 и разрешают величине ошибки суммироваться в блоке 13 с искаженным 40 элементом 7.1 с выхода седьмой ячейки регистра 3 (фиг. 4). Скорректированные данные в виде (а)-разрядного числа снимашт с выходов блока 13 от момента коррекции и до конца текущего тактового интервала (заднего фронта режущего тактового импульса), Очередность появления данных на выходе устройства проиллюстрирована на фиг. 4 р. При этом первые семь 3-разрядные группы являются скорректированными сигналами данных, а две последние группы - контрольные разряды, иэ которых первую группу к 1.1 устройство не способно скорректировать в случае ошибки в ней. Вторую группу контрольных разрядов не корректируют. Как указывалось, в коррекции контрольных разрядов данного кода нет необходимости, поскольку их обычноигнорируют,Во время считывания с элементовпервой кодовой комбинации по мере освобождения регистров 1-3 в них записывают новую кодовую комбинацию.Коррекцию ошибки на другой позициирегистра 3 осуществляют аналогично.Пусть, например, искажен элементкода на третьей позиции второй кодо"вой комбинации. После записи в регистре 3 всей кодовой комбинации на выходе сумматора 6 присутствует величина ошибки, а навыходе блока 8 -номер"три" искаженной позиции. По переднему фронту очередного тактового импульса эту информацию записывают импульсом с выхода элемента И 12 в регистр 4 и во второй счетчик 1 О. Потекущему и следующим тактовым импуль"сам осуществляют выдачу данных с выходов 16 устройства получателю, атакже сдвиг и запись элементов новой кодовой комбинации в регистры1-3. При этом в предварительно установленном в состояние 3, = 011втором счетчике 10 подсчитывают числосдвигов данных в регистрах 1-3вплоть до состояния к=7, когда навкод.блока 13 с выхода последней ячейки х регистра 3 поступит искаженный элемент второй кодовой комбинации, имеющий третью позицию 3.2 (всоответствии с второй строкой матрицы Н).Выходными сигналами счетчика 10 всостоянии к=7 отпирают блок 11 и разрешают в этот момент величине ошибки,с выхода регистра 4 суммироваться вбпоке 13 с искаженным элементом 3.2второй кодовой комбинации. Другиегруппы разрядов по мере их поступления на блок 13 суммируют с .Ф так,как первым после коррекции тактовымимпульсом изменяют состояние счетчика10 и запирают блок 11 элементов.Если ошибка не происходит вовсе,либо произошла ошибка во второй группе контрольных разрядов, то в регистр4 запишется величина ошибки "0" и вовремя коррекции независимо от состояния счетчика 1 О все группы разрядов,поступающие на вход блока 13, будутсуммироваться с нулем, что никак ихне изменит.В предлагаемом устройстве вместодешифратора обратной величины и блока умножения двух величин известногоустройства использован блок деления одной величины на другую, в котором в виде деления совмещено выполнение обеих названных операций. При этом по структуре, по количеству элементов и межэлементных связей блок 8 соответствует лишь блоку умножения двух величин в известном устройстве что приводит к существенному упрощению и экономии по меньшей мере ш многовходовых элементов И и инверторов НЕ (в общем счете 2 логических элементов) в результате исключения дешифратора обратной величины, Кроме того вместо ш-входового на к=в ф(2 -1) выходов дешифратора номера искаженной позиции и блока вентилей иа к ш"разрядных групп в известном устройстве в предлагаемом устройстве использованы второй счетчик 1 и блок 11 элементов И. Дешифратор в известном устройстве содержит ш инверторов НЕ и как минимум К=(2 -1) многовходовых элементов И со сложными межэлементными связями, а блок вентилей известного устройства содержит К групп по ш элементов И со слож" ными межэлементными связями. Эта часть известного устройства содержит, 5таким образом (ш+2-1+шК) логическкх элементов. В то же время в предлагаемом устройстве те же функции выполняют ш триггеров второго счетчика (10) и ш элементов И блока 11 р всего 2 ш элементов. Поэтому здесь выигрьпп составляет (ш+2 -1+шКш). Имеющийся в составе известного устройства блок сумматоров коррекции содержит к сумматоров по ш элементов ИСКЛЮЧАЮЩЕЕ ИЛИ каждый, например, как показано на фиг 3, а в предлагаемом устройстве использован только один такой сумматор коррекции, в результате чего выигрыш составляет ш(к) элементов. Дополнительные блоки предлагаемого устройства, которых нет в известном, содержат: регистр 4 величины ошибки - ш триггеров, элемент И 12 - один элемент И, первый счетчик 25 9 - (ш+1) триггеров. В итоге выигрышсоставляет 7 - Зс(2 +1)-(2 ш+1)-1.2 2 1.1 О ЦРО 2.1 1,1 в.г ю.г У У 93 7.1 И 5 Л Ф 1 У паг г г ювг Ю Сярейин 7 2 61 57 9.7 .7 27 21 ХЕ К 72 62 52 92 32 22 12 г 2 1 дактор К.Тупица Хехред А. Кравчук Корректор И.Иус Подписноео иэобретенинм и открытиям при ГКНТ СССР35, Раушская наб д. 4/5 ий комбинат "Патент",Ужгород, ул. Гагарина,10 оивводственно-издат каз 1803 Тираж 885 ЕИИПИ Государственного комитет 15035, Москва, 7039 1 Б 7 О 2 2 3 8