Декодер произведения кодов размерности 3d с запросами

Декодер произведения кодов размерности 3d с запросами

Иллюстрации

Показать все

Реферат

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

Известны устройства восстановления стираний и исправления ошибок, использующие индексы мягких решений символов для повышения достоверности приема информации (см. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. -М.: Техносфера, С. 103, …, 105, а также Д. Форни. Каскадные коды / Д. Форни. - М.: Мир, 1970. - 207 с. и А.А. Гладких. Основы теории мягкого декодирования избыточных кодов в стирающем канала связи. - Ульяновск: УлГТУ, 2010. - 379 с. ).

Кроме того, известны устройства использования гиперкодов или произведений кодов (см. Hunt A., «Hyper -Codes: High-Performance Low-Complexity Error-Correcting Codes», Master′s Thesis, Carleton University, Ottawa, Canada, defended March 25, 1998, a также Hunt A., Crozier S., Falconer D., «Hyper-Codes: High-performance Low-Complexity Error-Correcting Codes», 19-th Biennial Symposium on Communications, Ontario, Canada, pp. 263-267, May 31 - June 3, 1998) а также устройства по патентам РФ на изобретения №№2166235, 2209519, 2209520, 2256294, 2344556).

Наиболее близким устройством такого же назначения является декодер с исправлением стираний (см. патент РФ на изобретение №2344556), содержащий блок приема, один выход которого через анализатор сигналов подключен к накопителю, а другой подключен к входу накопителя кодовой комбинации, выход которого подключен к первому входу блока исправления стираний, отличающийся тем, что введены коммутатор проверок, блок определения кластера, блок коррекции кластера, блок прямых координат, блок инвариантных координат и блок сравнения, выход которого подключен ко второму входу блока исправления стираний, при этом первый вход коммутатора проверок подключен к выходу накопителя, второй вход коммутатора проверок подключен к выходу накопителя кодовых комбинации, а выход подключен к одному из входов блока определения кластера, а также к входу блока прямых координат, один выход которого через блок инвариантных координат подключен к третьему входу блока сравнения, второй вход которого подключен к выходу блока прямых координат, при этом первый выход блока определения кластера подключен к входу блока коррекции кластера, выход которого подключен к другому входу блока определения кластера, второй выход которого подключен к первому входу блока сравнения.

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

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

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

Сущность изобретения поясняется чертежом, на котором изображена схема изобретения.

Устройство содержит блок 1 приема, первый выход которого подключен к блоку 2 статистических оценок, а второй выход - к первому входу блока 3 накопителя строк. Оно отличающийся тем, что дополнительно введены блок 4 обработки матриц, декодер 3D 5, блок 6 ярлыков, блок 7 выборки данных и блок 8 запросов. При этом один выход блока 2 статистических оценок подключен к второму входу накопителя строк 3, а его выход подключен к первому входу блока 4 обработки матриц. Второй вход этого блока подключен к другому выходу блока 2 статистических оценок, при этом первый, второй и третий выходы блока 4 обработки матриц подключены соответственно к первому входу декодера 3D 5, к другому входу блока 7 выборки данных и к второму входу блока 6 ярлыков, первый вход которого подключен к третьему выходу блока 1 приема, а первый выход блока 6 ярлыков через один вход блока 7 выборки данных подключен к второму входу декодера 3D 5, тогда как второй выход блока 6 ярлыков подключен к входу блока 8 запросов.

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

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

где №i - номера ярлыков соответствующих матриц.

Первые три матрицы представляют собой произведения кодов размерности 2D (проверка четности по строкам и по столбцам), четвертая матрица является проверкой четности одноименных элементов первых трех матриц и в совокупности с ними определяет произведение кодов размерности 3D. После передачи первых трех матриц по каналу с помехами каждый символ двоичной последовательности фиксируется блоком 1 приема в виде двух синхронных между собой последовательностей. Первая последовательность представляется множеством жестких решений в виде логических нулей или единиц, а вторая последовательность представляется множеством мягких решений, номера которых соответствуют номерам последовательностей жестких решений в каждой матрице. Жесткие решения и объединенные с ними мягкие решения через первый выхода блока 1 приема передаются в блок 2 статистических оценок, а через второй выход блока 1 приема - построчно в накопитель строк 3. Мягкие решения на основе параметров принятого сигнала, получаемых в блоке 1, формируются в виде целочисленных значений, например, в диапазоне от 0 до 7 (А.А. Гладких. Основы теории мягкого декодирования избыточных кодов в стирающем канала связи. - Ульяновск: УлГТУ, 2010. - 379 с. - см. 211 с). В блоке 1 информационные единицы (жесткие решения) заменяются на знак (-): а нули соответственно заменяются на знак (-). В результате указанных операций в блоке 2 будут зафиксированы индексы мягких решений 5, 1, 7, 7, для которых определяется выборочное среднее и дисперсия. Выборочное среднее значение оценивается по формуле M ( λ ) = ( 1 / n ) ∑ i = 1 n | λ i | , где λ_i - мягкие решения символов j-й строки, а дисперсия - как σ 2 ( λ ) = ( 1 / n − 1 ) ∑ i = 1 n ( | M ( λ ) | − | λ i | ) 2 , в частности для j=1 будет получено: M(λ_j=1)=5 и σ²(λ_j=1)=8. Эти данные из блока 2 через один его выход передаются в блок 3, в котором для символов строки оценивается выполнение четности. В системе 3D это означает проверку и корректировку данных по оси «0х». Таким образом, в первой строке матрицы с ярлыком №1 правило четности не выполняется. При выполнении четности в анализируемой строке матрицы ей присваивается индекс: sign=(+), в противном случае: sign=(-). Для данных вида +5-1+7+7 будет получено

или в виде +5 -1 +7 +7 -5 8. В полученных данных правило четности не выполняется, поэтому накопитель строк 3 оценивает индексы надежности принятых символов строки и инвертирует знак у символа с наименьшим значением индекса при этом инвертируемому символу присваивают максимальный индекс, что в последующем позволяет эффективно осуществить проверку по столбцам. В результате будет получено +5 +7 +7 +7 +5 8. Данные первой строки передаются в блок 4 обработки матриц. Во второй строке матрицы с ярлыком №1 условие четности выполняется и ее измененные данные вместе со статистическими параметрами из блока 2 передаются в блок 4. В ходе обработки третей строки правило четности выполняется, но статистические характеристики строки оказываются низкими. После накопления всех данных матрица с ярлыком №1 обрабатывается в блоке 4, где осуществляется проверка данных матрицы по столбцам. Что в системе 3D оценивается, как проверка по вертикальной оси «0z».

В матрице не выполняются условия четности во втором и четвертом столбце, поэтому в блоке 4 осуществляется исправление ошибок и корректировка индексов матрицы. Они принимают вид

В прямых скобках [·] показано среднее значение индексов откорректированной матрицы, в угловых скобках 〈·〉 показано среднее значение дисперсии для данной матрицы. Откорректированная таким образом матрица через первый выход блока 4 направляется для дальнейшей обработки в декодер 3D - блок 5. В результате приема матрицы с ярлыком №2 образуются данные, которые невозможно целенаправленно обработать в блоках 3 и 4 из-за низких показателей индексов мягких решений и невыполнения для многих строк и столбцов условий четности. Неудовлетворительный прием элементов матрицы из-за влияния эффекта группирования ошибок в канала связи отражается в низком среднем значении индексов по всем показателя

Матрица с такими данными через второй выход блока 4 направляется в блок выборки данных 7, а ярлык этой матрицы через третий выход блока 4 направляется в память блока ярлыков 6. Блок приема 1, не нарушая очередности поступления матриц, продолжает обрабатывать данные матрицы с ярлыком №3, а блок 6 через свой второй выход находится в готовности сформировать запрос на повторение матрицы с ярлыком 2. Пусть матрица с ярлыком №3 в результате обработки в блоках 2, 3 и 4 принимает вид

Очевидно, что среди всех принятых матриц матрица с ярлыком №2 для своего восстановления требует повторной передачи. Запрос на повторение этой матрицы не отправляется в блок 8 запросов до тех пор, пока не сложится полная картина для всех матриц кода 3D. Если среди всех матриц кода 3D с низкими параметрами окажется только одна, то значения символов такой матрицы могут быть восстановлены за счет проверок четности одноименных символов в строках всех матриц, т.е. проверок в системе 3D по оси «0у». Блоку 6 ярлыков известны все ярлыки, для которых необходимо организовать повторение информации (повторение матриц), а также номер последнего ярлыка в системе 3D, к которому относится матрица проверок по оси «0z». Если в блоке 6 нет ни одного ярлыка (нет необходимости повторять данные), то блок 6 через свой второй выход отправляет сигнал в блок запросов 8, который отменяет передачу последней матрицы: что обеспечивает повышение эффективности декодера по скорости обмена. Если в блоке 6 ярлыков находится более одного ярлыка, то блок 6 ярлыков через свой второй выход передает соответствующую информацию в блок 8 запросов, при этом в первую очередь запрашивается повторение той матрицы, у которой параметры [·] и 〈·〉 оказались хуже, чем у других (другой матрицы), зафиксированных в блоке 7 выборки данных. Блок 8 запросов запрашивает повторение требуемой матрицы. В процедуре повтора данных запрашиваемой матрицы присутствует ярлык повторяемой матрицы, при этом блок 1 приема через свой третий выход отправляет ярлык на первый вход блока 6 ярлыков. Это означает, что сравнение данных в блоке 7 выборки данных будет осуществляться именно для запрашиваемой матрицы. Обработка данных для повторной матрицы в блоках 2, 3 и 4 декодера не отличается от описанного. Таким образом, матрица с ярлыком №2 после первичной обработки хранится в блоке 7 выборки данных в виде:

Пусть после повторной передачи элементы этой матрицы принимают вид:

Коррекция в столбце (строке) осуществляется по правилу:

где sign[·] возвращает значение своего аргумента, L[λ_1,2) - мягкие решения для символов а_i,j, занимающие одноименные позиции в сравниваемых матрицах и участвующих в формировании проверки на четность при первоначальном приеме матрицы L(λ₁) и при ее повторном приеме L(λ₂), L(λ_p) - мягкое решение для проверочного символа. Очевидно, что в любых условиях приема сравниваемых элементов матриц значение L(λ₁) должно быть L(λ_p)=-7. Поэтому (см. Гладких А.А., Линьков И.С. Оптимизация процедуры итеративных преобразований данных // Автоматизация процессов управления. №3(29) 2012, С. 3-7) при выполнении правила четности блок 7 выборки данных оценивает сравниваемый символ по правилам: если знаки и значения индексов совпадают, то принимается решение о сохранении знака и значения индекса, например +6 и +6→+6, если знаки одинаковы, а значения индексов различны, то сохраняется общий знак индексов, но выбирается больший по абсолютной величине индекс, например -3 и - 7→-1, если знаки различны, то выбирается знак и индекс с большим по абсолютному значением, например +2 и -5→-5, - если знаки различны, но значения индексов одинаковы, то символу присваивается значение 0 и знак для него не устанавливается. В результате сравнения по таким правилам первоначально принятых данных матрицы с ярлыком №2 с данными при ее повторной передаче формируется матрица вида и

Особенностями образовавшейся матрицы является наличие нулевых ИМР (стираний) и невыполнение четности для тех строк и столбцов, которые содержат стирания, невыполнение правила четности во второй строке. Восстановление символов начинается с первой строки, имеющей наибольшую дисперсию (10,25). Проверочный символ с индексом 0 заменяется на значение -7, при этом индикацией правильного выполнения операции является подтверждение проверки четности с достаточно надежным индексом достоверности+5.

На втором шаге блок 7 выборки данных исправляет стирание в третьей строке (максимальное значение дисперсии среди строк, для которых не выполняется условие четности). Матрица приобретает вид:

На третьем шаге меняется знак у второго элемента второй строки, поскольку правило четности не выполняется только для этого элемента и по строке и по столбцу. После восстановления матрица с ярлыком №2 передается в декодер 3D, где занимает свой раздел памяти.

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

Невыполнение правила четности во втором и третьем столбце матрицы оказывается трудно разрешимым в рамках одной матрицы из-за равенства показателей М(2), а выполнение запроса оказывается нецелесообразным по причине высоковероятного восстановления скрытых ошибок за счет параметров кода 3D.

В результате обработки всех матриц в декодере 3D 5 формируются данные

Декодер 3D в ходе обработки данных записывает их в виде матриц такой же размерности, как все предыдущие, с той лишь разницей, что каждая матрица представляет совокупность одноименных столбцов матриц всех обработанных ярлыков. Например, в матрице с ярлыком №4 возникли трудности восстановления символа в столбцах два и три. В блоке 5 вторые столбцы создадут совокупность символов вида, которая показывает, что условие четности не выполняется только в третьей строке и четвертом столбце. Происходит однозначное восстановление значения искаженного символа. Аналогичным образом проверяются на четность другие группы столбцов, в частности осуществляется восстановление третьего столбца матрицы с ярлыком №4. Пример преобразования группы вторых столбцов показан ниже.

В блоке 5 возможно объединение результатов по строкам.

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

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