УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ЛИНЕЙНЫХ КОДОВ Российский патент 1995 года по МПК H03M13/00 

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

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

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

Например, достаточно эффективными в настоящий момент являются декодеры, реализующие алгоритм Витерби (АВ) и активно используемые в спутниковых и космических каналах США, Японии и Западной Европы. Это теоретически оптимальный алгоритм по вероятности ошибки, к тому же он обеспечивает хорошие результаты при приеме без оценки достоверности и еще лучше при приеме с оценкой достоверности.

Однако из-за экспоненциального роста сложности реализации АВ его применимость ограничивается только очень короткими кодами.

С длинными кодами позволяют работать декодеры каскадных кодов (КК). Так как эти коды имеют очень большое кодовое расстояние, при малом уровне шума они позволяют получить очень малые вероятности ошибок на выходе.

Однако при большом уровне шума их эффективность оказывается невысокой из-за того, что код в целом фактически декодируется далеко не оптимально. Только при использовании АВ во внутреннем коде характеристики КК будут приемлемыми по достоверности, но тогда и весь КК будет обладать недостатками АВ.

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

Однако устройство обеспечивает довольно низкую достоверность декодирования, что ограничивает его использование лишь в каналах с низким уровнем помех (Р_о ≅ 0,01).

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

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

Известна система обнаружения и исправления ошибок для сверточных кодов [2] декодер которой содержит блок разделения символов, один выход которого соединен с комбинационным сумматором и последовательно связанными между собой информационным регистром, элементом задержки и сумматором. Второй выход блока разделения символов соединен с последовательно связанными между собой комбинационным сумматором и проверочным блоком. Выход проверочного блока связан с вторым входом сумматора. Информационный регистр выходами поразрядно связан с комбинационным сумматором. Вход блока разделения символов является входом декодера системы, а выход сумматора выходом всей системы.

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

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

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

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

Это дает возможность повысить достоверность декодирования по меньшей мере в 100 раз.

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

Это позволяет повысить достоверность декодирования еще в 3-10 раз.

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

Это обеспечивает еще более высокий уровень достоверности декодирования.

На фиг. 1 изображена структурная схема устройства; на фиг.2 простейшая структурная схема проверочного блока; на фиг.3 структурная схема проверочного блока, вариант; на фиг.4 блок-схема проверочного блока, вариант; на фиг.5 блок-схема реализации устройства, вариант.

Устройство для декодирования линейных кодов содержит блок 1 разделения символов (фиг.1), вход а которого является входом всего устройства, а информационный выход b которого соединен с последовательно связанными между собой информационным регистром 2₁, элементом 3₁ задержки и сумматором 4₁ первой ступени I декодирования, а также с последовательно связанными между собой комбинационным сумматором 5 и проверочным блоком 6₁ первой ступени 1 декодирования. Проверочный вход с блока 1 разделения символов соединен с комбинационным сумматором 5, а поразрядные выходы информационного регистра 2₁ также соединены с комбинационным сумматором 5. Выход d₁ проверочного блока 6₁ соединен с сумматором 4₁, выход f₁ которого является информационным выходом ступени I декодирования. Выход е₁ проверочного блока 6₁ является проверочным выходом ступени 1 декодирования.

Ступень 1 декодирования соединена с по меньшей мере еще одной дополнительной ступенью II декодирования, причем информационный выход f₁ ступени I декодирования соединен с последовательно связанными между собой информационным регистром 2₂, элементом 3₂ задержки и сумматором 4₂. Проверочный выход е₁ ступени 1 декодирования соединен с проверочным блоком 6₂, выход d₂ которого соединен с сумматором 4₂, а выходы f₂ сумматора 4₂ и е₂ проверочного блока 6₂ являются соответственно информационным и проверочным выходами ступени II декодирования.

Выход f_N последней степени N декодирования является выходом всего устройства.

Проверочный блок 6 (фиг.2) любой ступени содержит синдромный коммутатор 7, вход g которого является входом проверочного блока 6, а поразрядные входы и выходы синдромного коммутатора 7 связаны соответственно с поразрядными выходами и входами синдромного регистра 8. Поразрядные выходы синдромного регистра 8, кроме того, связаны с коммутатором 9 решающего устройства, который связан с решающим устройством 10, одним из входов которого является вход g проверочного блока 6, а выход d соединен с входом синдромного коммутатора 7 и является информационным выходом проверочного блока 6, а выход е последнего разряда синдромного регистра 8 является проверочным выходом проверочного блока 6.

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

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

Устройство для декодирования линейных кодов работает следующим образом.

На вход а устройства последовательно поступают информационные и проверочные символы линейного кода. Блоком 1 разделения символов они делятся на два потока информационные b и проверочные с. Информационные символы b заполняют по сдвиговым входам информационный регистр 2₁, а вместе с проверочными символами с поступают в комбинационный сумматор 5, где определяется разница между полученными информационными b символами и образованными из полученных проверочных символов с, которая по сдвиговым входам заполняет синдромный регистр 8₁ проверочного блока 6₁. Поразрядные выходы синдромного регистра 8₁ поступают в коммутатор 9₁ решающего устройства, а из него на вход решающего устройства 10₁, куда поступает сигнал со входа g₁ проверочного блока 6₁ и где определенные разряды суммируются, а сумма сравнивается с некоторым пороговым значением, устанавливаемым в зависимости от сочетания значений входов решающего устройства 10₁, и превышение которого формирует решение об изменении декодируемого символа, что и происходит на выходном сумматоре 4₁ ступени 1 декодирования, куда одновременно поступают сигнал d₁ с выхода решающего устройства 10₁ и информационный сигнал, прошедший элемент 3₁ задержки. Этот декодированный символ f₁ поступает в сдвиговый информационный регистр 2₂ следующей ступени II декодирования, в синдромный регистр 8₂ которой передается измененное в соответствии с выводом решающего устройства 10 значение е₁ последнего разряда предыдущего синдромного регистра 8₁. Решающее устройства 10₂ этой II cтупени декодирования на основе установленного порога принимает свое решение d₂ о необходимости коррекции декодируемого символа, передавая этот символ f₂ и последний разряд е₂ своего синдромного регистра 8₂ в следующую степень III декодирования, и так далее.

Проверочный блок 6 любой ступени (фиг.3) может дополнительно содержать разностный регистр 11, вход h которого является дополнительным входом проверочного блока 6 и выход которого связан со входом решающего устройства 10 и с сумматором 12, второй вход которого связан с выходом d решающего устройства 10. Выход q сумматора 12 является дополнительным входом проверочного блока 6.

Вход h₂ первой дополнительной ступени II декодирования соединяется с источником уровня логического нуля, а выход q_N последней ступени N декодирования не используется.

В этом случае работа устройства (фиг.3) несколько усложняется тем, что на вход решающего устройства 10_i поступает дополнительно выходной сигнал разностного регистра 11_i, который к тому же, суммируясь на сумматоре 12_i с сигналом на выходе d_i решающего устройства 10_i, образует сигнал q_i для заполнения разностного регистра 11_i+1 следующей ступени (i+1)-ой декодирования.

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

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

На фиг.5 представлена блок-схема простейшего варианта выполнения устройства для декодирования сверточных кодов информационной двоичной последовательности с длиной кодового ограничения 14, кодовым расстоянием 5, кодовым полиномом 1 + x + x⁴ + x⁶ и скоростью передачи 1/2. Устройство содержит четыре ступени декодирования. Решающие устройства реализуются пороговыми элементами, которые имеют пороговые значения, соответственно, 3 3 2 2.

В сумматоре А складываются проверочные символы, поступающие из канала (ключ к в положении "а с") и подсчитываемые с' на сумматорах В₁, В₂, В₃ из информационных символов b, заполняющих информационный регистр RG2₁ (ключ к в положении "а в"). Их сумма, которая по mod₂ даст 0 при отсутствии искажения в канале и I если искажение произошло, поступает в синдромный регистр RG8₁, причем единственная ошибка в проверочных символах вызовет появление единицы в синдромном регистре RG8₁ на месте, соответствующем ошибочному проверочному символу, что приведет к тому, что на любом из 13 сдвигов синдромного RG8₁ (и информационного RG2₁) регистра сумма единиц на пороговом элементе 10₁ не превысит 1 < 3 и сигнал изменяться не будет.

Если ошибка произошла в информационном символе, например в девятом разряде, то синдромный регистр RG8₁ получит заполнение вида 0001010011000, которое даст сумму проверок на пороговом элементе 10₁ 4 > 3 только при таком положении сдвиговых регистров RG2₁ и RG8₁, когда будет декодироваться символ, соответствующий девятому разряду начального заполнения информационного регистра RG2₁, т.е. инвертирован на сумматоре D₁ будет именно ошибочно принятый информационный символ.

Первая ступень декодирования обеспечивает вероятность ошибки декодирования Р_в(е) ≈2 ˙ 10^-4 при работе в канале с вероятностью ошибки р_о < 0,01, что существенно хуже теоретически возможной величины для данного кода.

Введение в схему еще трех ступеней декодирования, куда передаются состояния информационного регистра RG2_i и старшего разряда е_i синдромного регистра RG8_i пре- дыдущей ступени i декодирования, позволяет получить Р_в(е) ≈10^-5.

Введение в схему разностного регистра (фиг.3) и умножителей на весовые коэффициенты (фиг. 4) позволяет довести показатели декодирующего устройства для более мощных кодов до Р_в(е) ≈10^-5 при Р_о ≈0,056.

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

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

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

Основным достоинством устройства является высокий уровень достоверности, а именно при вероятности ошибки на входе 0,01-0,1 устройство обеспечивает на выходе 10^-4 10^-7 и менее в среднем на каждый символ, в том числе и в телефонных сетях.

Совершенно новый качественный уровень помехоустойчивости достигнут на особо простых и однородных элементах.

Устройство довольно легко реализуемо в виде заказных и матричных БИС, микропроцессорных плат и программными средствами.

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

1. УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ЛИНЕЙНЫХ КОДОВ, включающее блок 1 разделения символов, информационный выход b которого соединен с комбинационным сумматором 5 и с последовательно связанными между собой информационным регистром 2₁, элементом 3₁ задержки и сумматором 4₁, а проверочный выход c блока 1 разделения символов соединен с последовательно связанными между собой комбинационным сумматором 5 и проверочным блоком 6₁, причем поразрядные выходы информационного регистра 2₁ связаны с комбинационным сумматором 5, а проверочный блок 6₁ состоит из последовательно и поразрядно связанных между собой синдромного коммутатора 7₁, синдромного регистра 8₁, решающего устройства 10₁ с коммутатором 9₁, причем поразрядные выходы синдромного регистра 8₁ связаны с синдромным коммутатором 7₁, первый вход g₁ которого является входом решающего устройства 10₁ и всего проверочного блока 6₁, а второй вход связан с выходом решающего устройства 10₁, являющимся выходом d₁ проверочного блока 6₁, который связан с сумматором 4₁, причем вход a блока 1 разделения символов является входом всего устройства, отличающееся тем, что устройство дополнительно снабжено по меньшей мере одной ступенью 11 декодирования, включающей в себя проверочный блок 6₂ и последовательно связанные между собой информационный регистр 2₂, элемент 3₂ задержки и сумматор 4₂, вход каждого из которых соединен с проверочным блоком 6₂, причем вход f₁ информационного регистра 2₂ и вход e₁ проверочного блока 6₂ соединены соответственно с выходами сумматора 4₁ и проверочного блока 6₁ первой ступени 1 декодирования и являются входами всей ступени 11 декодирования, а ее выходами являются выход f₂ сумматора 4₂ и сдвиговый выход e₂ синдромного регистра 8₂, причем количество N ступеней i декодирования зависит от необходимой достоверности декодируемого сигнала и выходом всего устройства является выход f_N сумматора 4_N последней ступени N декодирования. 2. Устройство по п.1, отличающееся тем, что проверочный блок 6 дополнительно снабжен последовательно связанными между собой разностным регистром 11 и сумматором 12, причем вход h разностного регистра 11 и выход q сумматора 12 являются соответственно входом h и выходом q проверочного блока 6, а выход разностного регистра 11 соединен с входом решающего устройства 10, выход d которого соединен с вторым входом сумматора 12.