СПОСОБ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ЦИФРОВЫХ ДАННЫХ Российский патент 2016 года по МПК H03M13/05 

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

Одной из существенных проблем, встающих перед разработчиком системы обмена цифровой информацией, является обеспечение низкой вероятности ошибок. При этом основным ресурсом повышения достоверности передачи данных при таком обмене является помехоустойчивое кодирование, т.е. применение на передающем конце избыточных кодов, а на приемном конце - процедур декодирования с исправлением возможных ошибок (см. например, [1, глава 6], а также [2]…[4]).

О терминологии. Каждая частная процедура, входящая в совокупность процедур кодирования/декодирования, в общем случае состоит из двух фаз; в первой фазе осуществляется кодирование/декодирование без применения технических мероприятий, обеспечивающих исправление ошибок (см., например, [1, раздел 3.1.2.]) - далее называем эту фазу соответственно предварительным кодированием/декодированием (предварительное декодирование именуют также детектированием), а во второй фазе - введение при передаче избыточных символов в каждый результат предварительного кодирования и исправление при приеме ошибок, возникших при предварительном декодировании, - далее называем эту фазу соответственно помехоустойчивым кодированием/декодированием; в рамках настоящей заявки рассматривается объект, реализующий совокупность операций только второй фазы (т.е. помехоустойчивого) кодирования/декодирования. Данный подход в теории помехоустойчивого кодирования/декодирования (предполагающий рассмотрение вопросов помехоустойчивого кодирования/декодирования в отрыве от указанной первой фазы кодирования/декодирования) является общепринятым.

Известны способы помехоустойчивого кодирования/декодирования данных, обеспечивающие исправление как одиночных, так и кратных ошибок (см., например, [1], [5]).

При передаче данных с Q-арным кодированием [1, раздел 6.1.2], представляющих собой блоки информационных P-разрядных символов (при P=log₂Q), ошибка, возникающая при предварительном декодировании какого-либо P-разрядного символа, влечет за собой ошибки в определении от одного до всех P бит (разрядов) этого символа (битовых ошибок). (Под Q-арным понимается такое кодирование, при котором каждый канальный символ несет информацию об одной из Q альтернатив сообщения). Таким образом, ошибка при предварительном декодировании всего в одном символе блока таких символов приводит к неконтролируемому множеству битовых ошибок. Проблема исправления ошибок в указанном случае дополнительно усугубляется при возникновении при предварительном декодировании ошибок в двух и более P-разрядных символах блока. В данных ситуациях, какие бы совершенные помехоустойчивые коды не использовались, они не могут гарантировать высокой достоверности приема. Основная причина такого положения - в резком снижении корректирующих способностей кодов при наличии множественных ошибок в блоке (даже и при использовании методов кодирования, рассчитанных на исправление множественных или кратных ошибок). Кроме того, с ростом количества возможных ошибок имеет место значительный рост вычислительной сложности декодирования с их исправлением.

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

Таким образом, недостатком аналогов является низкая достоверность передачи данных при их Q-арном кодировании (при Q>1).

Наиболее близким по технической сущности к заявляемому объекту является способ помехоустойчивого кодирования/декодирования цифровых данных, в основе которого лежит так называемый «прямоугольный код» [7, с. 33] (см. также [1, раздел 6.3.3.2]). Этот способ рассматривается в качестве прототипа. Прототип рассчитан на кодирование бинарных (одноразрядных) символов, поэтому далее используемый в источнике [7, с. 33] термин «символ» уточняем как «бинарный символ». Прототип предусматривает представление каждого из блоков, содержащих по K бинарных символов передаваемого сообщения, в виде прямоугольника размером M·N. Затем к каждой строке указанного прямоугольника, состоящей из N бинарных символов, добавляется бинарный символ проверки на четность, так что длина строки становится равной N+1 бинарным символам.

Аналогично этому к каждому столбцу также добавляется по одному проверочному бинарному символу. Таким образом, первоначальный прямоугольник из M·N бинарных символов превращается в прямоугольник из (M+1)·(N+1) бинарных символов (при этом в нем может отсутствовать символ, находящийся на пересечении (M+1)-й строки и (N+1)-го столбца). Далее в прототипе на приемной стороне (после предварительного декодирования) посредством проверки на четность определяются строка и столбец, в которых имеется ошибка (если она вообще имеется), и конкретный ошибочный бинарный символ, являющийся для этой пары строки и столбца общим, т.е. бинарный символ, находящийся на их пересечении. Исправление ошибки производится изменением кода этого бинарного символа на дополнительный (т.е. с «1» на «0» или наоборот).

Как отмечено выше, приведенное изложение прототипа предполагает передачу бинарных символов. В случае передачи Q-арных символов, т.е. в случае представления каждого символа P-разрядным кодом, реализация прототипа предполагает расположение разрядов каждого символа в строке или в столбце прямоугольника (при этом прямоугольник имеет размеры, например, M·N=K·P). Тогда в случае возникновения ошибки при предварительном декодировании всего одного символа в соответствующим этому символу строке или в столбце указанного прямоугольника будут иметь место ошибочно определенные биты этого символа в количестве от 1 до P штук. При этом в случае четного количества указанных ошибочно определенных бит проверка на четность ошибок не выявит, и тогда прототип исправление ошибок не обеспечивает. Последнее имеет место с вероятностью 0.5. Как отмечено выше, проблема исправления ошибок в указанном случае дополнительно усугубляется при возникновении при предварительном декодировании ошибок в двух и более P-разрядных символах.

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

Далее вместо термина «прямоугольник» используется представляющийся более точным термин «матрица». Кроме того, ниже в ряде случаев, когда речь идет об P-разрядном (т.е. Q-арном) символе, используется термин просто «символ» (в отличие от термина «бинарный символ»).

Целью заявляемого способа является повышение достоверности передачи при обмене данными.

Поставленная цель достигается тем, что в способе помехоустойчивого кодирования и декодирования цифровых данных, состоящем в представлении на передающей стороне каждого блока данных, содержащего последовательность из K информационных бинарных символов, в виде матрицы, содержащей M строк и N столбцов, и добавлении к этому блоку Θ=M+N избыточных бинарных символов, причем правило формирования каждого из M избыточным бинарных символов обеспечивает проверку на четность массива информационных бинарных символов соответствующей строки указанной матрицы, а правило формирования каждого из оставшихся N избыточных бинарных символов обеспечивает проверку на четность массива информационных бинарных символов соответствующего столбца этой матрицы, а на приемной стороне - в определении номеров строки и столбца указанной матрицы, в которых на основе проверки на четность обнаружена ошибка, определении бинарного символа, являющегося для указанных строки и столбца общим, и изменении кода этого бинарного символа на дополнительный, введены изменения, состоящие в том, что количество матриц, в виде которых представляется блок из K подлежащих передаче информационных P-разрядных символов, выбирают равным разрядности каждого из этих символов, причем каждую p-ю (при p=1…P) из них компонуют из p-х разрядов информационных символов, указанные операции добавления избыточных символов на передающей стороне и определения номеров строки и столбца, в которых на основе проверки на четность обнаружена ошибка, определения бинарных символов, являющихся для указанных строки и столбца общими, и изменении кодов этих бинарных символов на дополнительные на приемной стороне выполняют для каждой из P матриц, на передающей стороне формируют Θ P-разрядных избыточных символов из P совокупностей Θ указанных бинарных избыточных символов, а на приемной стороне реализуют представление каждого принятого блока данных в виде совокупности P матриц, содержащих по (M+1)·(N+1) бинарных символов каждая, кроме того, определяют P-разрядные символы, в которых произошли ошибки, причем каждый их таких символов определяется по той матрице, в которой ошибка обнаружена только в одном столбце и одной строке, а каждая из совокупности операций изменения кода каждого бинарного символа осуществляется над совокупностью бинарных символов, принадлежащих тем P-разрядным символам, в которых произошли ошибки.

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

Блок-схема, иллюстрирующая заявляемый способ, приведена на фиг. 1, где обозначены:

1.1…1.P - представление каждого блока данных, содержащего последовательность из K бинарных символов, в виде матрицы, содержащей M строк и N столбцов (это относится к каждой p-й из операций 1.1…1.P);

2.1…2.P - добавление к каждой p-й (p=1…P) матрице M=N избыточных бинарных символов;

3.1…3.Θ - формирование Θ P-разрядных избыточных символов;

4.1…4.P - представление каждого принятого блока данных в виде совокупности P матриц, содержащих M+1 строк и N+1 столбцов бинарных символов;

5.1…5.P - определение в каждой p-й матрице номеров строки и столбца, в которых обнаружены ошибки,

6.1…6.P - определение в каждой p-й матрице бинарных символов, являющихся для определенных при выполнении соответствующей из операций 3.1…3.P строк и столбцов общими;

7.1…7.P - изменение кодов ошибочных бинарных символов, определенных при выполнении соответствующей из операций 5.1…5.P, на дополнительные;

8 - определение символов, в которых произошли ошибки.

Все операции заявляемого способа реализуются программируемыми устройствами цифровой обработки сигналов (например, микрочипами).

Содержание совокупности операций 1.1…1.P (представление каждого блока данных, содержащего последовательность из K бинарных символов, в виде матрицы, содержащей M строк и N столбцов) однозначно соответствует наименованию этой совокупности операций. Входными данными для этой совокупности операций являются блоки подлежащих передаче P-разрядных информационных символов (эти символы сформированы в результате упомянутого выше предварительного кодирования, которое, как оговорено выше, выходит за рамки заявляемого способа).

Каждая p-я (при p=1…P) из них (т.е. операция 1.p) реализуется над массивом одноименных (например, p-x) разрядов блока из K P-разрядных информационных символов полностью аналогично тому, как подобная операция реализуется над массивом также одноименных разрядов в прототипе (с той только разницей, что в прототипе имеет место условие P=1). При этом (для каждого p) p-е разряды М первых символов передаваемого блока (т.е. тех символов, с которых это блок начинается) располагаются в первой строке p-й матрицы, эти же разряды последующих M символов блока - во второй строке p-й матрицы и т.д… и так (при K=M·N) всего N раз при передаче каждого блока информационных символов. В итоге выполнения совокупности операций 1.1…1.P при помехоустойчивом кодировании текущего передаваемого блока информационных символов сформированы P матриц размером M·N, элементами которых являются одноразрядные (бинарные) символы. Далее предполагается, что во всех P матрицах бит (разряд) каждого символа помещен в одну и ту же позицию (т.е. является элементом одной и той же совокупности строки и столбца матрицы), «закрепленную» за этим символом. Закон соответствия между порядковыми номерами символов в блоке и позициями их бит в матрицах оговорен в настоящем абзаце выше.

На фиг. 1 условно показаны P связей между операциями 1.1…1.P и 2.1…2.P. При этом имеется в виду, что по каждой p-й из этих связей передается результат формирования указанной выше матрицы размерами M·N, сформированной по p-м разрядам P-разрядных символов блока.

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

Фактически совокупность операций 1.1…1.P реализует переформатирование массива данных в обеспечение дальнейшей реализации совокупности операций 2.1…2.P.

Содержание совокупности операций 2.1…2.P (добавление к каждой p-й (p=1…P) матрице M+N избыточных бинарных символов) состоит в следующем. В каждой строке каждой матрицы независимо осуществляется подсчет количества единиц. К тем строкам, в которых количество единиц оказалось четным (или нечетным), в качестве M+1-го (избыточного или проверочного) бита (бинарного символа) добавляется ноль (или соответственно единица). (Принцип контроля честности может быть и обратным). Аналогичная операция добавления проверочных битов осуществляется и по отношению к каждому столбцу каждой матрицы. В итоге выполнения данной операции сформированы P матриц (состоящих из бинарных символов) размерами по (M+1)·(N+1) каждая (это утверждение может быт уточнено следующим образом: в данной матрице размерами (M+1)·(N+1) на самом деле отсутствует элемент на пересечении (M+1)-й строки и (N+1)-го столбца), что несущественно.

На фиг. 1 условно показаны P выходов совокупности операций 2.1…2.P. При этом имеется в виду, что на каждый p-й из этих выходов поступает результат формирования массивов данных, содержащих все элементы p-й матрицы размерами (M+1)·(N+1), сформированной по p-м разрядам P-разрядных символов блока.

Содержание совокупности операций 3.1…3.Θ состоит в формировании Θ P-разрядных избыточных символов. В итоге выполнения каждой операции 3.θ-й из этих операций формируется θ-й P-разрядный избыточный символ, каждый p-й (p=1…P) разряд которого есть θ-й бинарный избыточный символ, сформированный при выполнении операции 2.p (напомним, что при выполнении операции 2.р формируются Θ=M+N бинарных избыточных символов, сформированных по совокупности p-х разрядов соответствующих информационных символов.

Говоря другими словами, при формировании Θ=M+N P-разрядных избыточных символов каждым p-м разрядом каждого m-го (m=1…М) из M избыточных P-разрядных символов является проверочный бинарный символ, добавленный при выполнении операции 2.p (p=1…P) в m-ю строку p-й матрицы, а каждым p-м разрядом каждого n-го (n=1…N) из N избыточных P-разрядных символов является проверочный бинарный символ, добавленный при выполнении операции 2.p (p=1…P) в n-й столбец p-й матрицы.

Выход совокупности операций 3.1…3. Θ показан на фиг. 1 многоканальным. При этом имеется в виду, что на этом выходе формируется поток, содержащий (при передаче каждого блока) последовательность из K информационных и Θ избыточных P-разрядных символов.

Далее приведено пояснение совокупности операций, выполняемых при передаче данных в промежутке между выходами совокупности операций 3.1…3.Θ и входами совокупности операций 4.1…4.P. Эта (т.е. поясняемая) совокупность операций в состав заявляемого способа не входит (т.к. к собственно помехоустойчивому кодированию/декодированию она не относится), но ее пояснение существенно для раскрытия принципа действия заявляемого способа.

Результаты выполнения совокупности операций 3.1…3.Θ передаются на приемную сторону системы связи (обмена данными) классически. (Иллюстрирующая это положение общая структурная схема способа передачи данных приведена в [1] перед каждой главой; при этом совокупность операций, составляющих заявляемый способ в [1], именуется как «канальное кодирование» (при передаче) и «канальное декодирование» (при приеме)). При этом условно показанная на фиг. 1 (на выходах совокупности операций 3.1…3.Θ) совокупность потоков данных перед непосредственно передачей в канал обмена (связи) объединяется в один поток данных. В этом потоке (при передаче каждого блока) последовательно во времени расположены K P-разрядных информационных символов передаваемого сообщения, а также Θ избыточных P-разрядных символов. Указанные информационные символы (они являются входными данными заявляемого способа) при выполнении совокупностей операций 1.1…1.P, 2.1…2.P и 3.1…3.Θ просто транслируются на выход совокупности операций 3.1…3.Θ и к ним в потоке добавляются указанные Θ избыточных P-разрядных символов.

На приемной стороне по принимаемым сигналам в результате выполнения операции предварительного декодирования (детектирования) так же классически осуществляется формирование потока данных. Последний содержит (при приеме каждого блока) K информационных P-разрядных символов, отличающихся от потока данных, подлежащих передаче (т.е. поступающих на общий вход совокупности операций 1.1…1.P) только с возможным несовпадением ряда битов вследствие ошибок, возникших при предварительном декодировании, а также Θ избыточных P-разрядных символов (которые также могут содержать ошибки, возникшие при предварительном декодировании).

На приемной стороне осуществляется предварительное декодирование каждого принятого блока символов.

Этим пояснения по выходящей за рамки заявляемого способа совокупности операций, выполняемых в системе связи при передаче данных в промежутке между выходами совокупности операций 3.1…3.Θ и входами совокупности операций 4.1…4.P, завершаются.

После предварительного декодирования на приемной стороне реализуется переформатирование принимаемого потока данных. Это переформатирование осуществляется в процессе выполнении совокупности операций 4.1…4.P (представление каждого принятого блока данных в виде совокупности P матриц) вначале путем преобразования K=M·N информационных P-разрядных символов в совокупность P матриц размерами M·N по правилу, полностью совпадающему с содержанием совокупности операций 1.1…1.P. В итоге этого действия по каждому передаваемому блоку сформированы те же P матриц, что и в итоге выполнения совокупности операций 1.1…1.P, но с возможными ошибками, возникшими при предварительном декодировании. Далее в эти матрицы добавляются бинарные избыточные символы, являющиеся соответствующими разрядами принятых в данном блоке избыточных P-разрядных символов. Правило распределения (размещения) разрядов принятых в данном блоке избыточных P-разрядных символов в указанных матрицах полностью определяется приведенным выше правилом формирования на передающей стороне избыточных P-разрядных символов по избыточным (проверочным) битам матриц (т.е. по тому правилу, по которому на передающей стороне из совокупности бинарных избыточных символов всех матриц были сформированы совокупности разрядов избыточных P-разрядных символов, на приемной стороне из разрядов избыточные P-разрядных символов сформированы избыточные бинарные символы всех матриц). В итоге выполнения последней операции сформированы P матриц, содержащих в каждых строке по N информационных символов и один избыточный, а в каждом столбце - по M информационных символов и также один избыточный, т.е. сформированы P матриц размерами (M+1)·(N+1).

Содержание совокупности операций 5.1…5.P (определение в каждой p-й матрице номеров строки и столбца, в которых обнаружены ошибки) состоит в следующем. В каждой строке каждой матрицы размерами (M+1)·(N+1), сформированной в результате выполнении совокупности операций 4.1…4.P, независимо осуществляется подсчет количества единиц. Те строки, в которых количество единиц оказалось четным, признаются не содержащими ошибок предварительного декодирования, а те строки, в которых количество единиц оказалось нечетным, признаются содержащими такие ошибки (т.е. в них обнаружены ошибки; указанное правило обнаружения ошибок соответствует приведенному выше описанию алгоритма формирования бинарных избыточных символов при выполнении операций 2.1…2.P). Номера строк каждой матрицы, в которых обнаружены ошибки, запоминаются.

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

В итоге выполнения совокупности операций 5.1…5.P по каждой матрице сформированы номера тех ее строк и столбцов, в которых обнаружены ошибки предварительного декодирования. Эти результаты далее используются для выполнения совокупности операций 6.1…6.P, а также 8 (возможен также эквивалентный вариант реализации заявляемого способа в котором при реализации операции 8 может быть использована и информация, выработанная в результате выполнения операций 6.1…6.P вместо операций 5.1…5.P).

Содержание совокупности операций 6.1…6.P (определение в каждой p-й матрице бинарных символов, являющихся для определенных при выполнении соответствующей из операций 5.1…5.P строк и столбцов общими) состоит в следующем. Пусть каждый бинарный символ, расположенный в m-й строке и в n-м столбце (т.е. являющийся для сочетания этих строки и столбца общим) каждой p-й матрицы, обозначен как βpmn. Тогда при обнаружении в некоторой p-й матрице ошибки в m₀-й строке и n₀-м столбце общим бинарным символом этой матрицы (называем его потенциально подлежащим корректировке) является символ βpm₀n₀. Результатами выполнения совокупности операций 5.1…5.P являются выявленные сочетания указанных трех индексов (это понятие ниже уточнено в Примечании) каждого потенциально подлежащего корректировке бинарного символа (в этой части заявляемый способ отличается от прототипа только тем, что данная операция производится одновременно над P матрицами, т.е. она многоканальна). Совокупность кодов бинарных символов всех матриц, а также все указанные выявленные сочетания трех индексов каждого потенциально подлежащего корректировке бинарного символа являются исходными данными для выполнения совокупности операций 7.1…1.P. Кроме того, как отмечено выше, все указанные выявленные сочетания трех индексов каждого потенциально подлежащего корректировке бинарного символа могут являться исходными данными и для выполнения операции 8.

Примечание. В том случае (случаях), когда ошибки предварительного декодирования произошли в двух бинарных символах хотя бы некоторой одной (p-й) матрицы и они принадлежат одной и той же строке (или одному и тому же столбцу), то при проверке на четность ошибка в этой строке (или соответственно столбце) указанной матрицы обнаружена не будет (поскольку при проверке на четность четное количество ошибок не выявляется). При этом в заявляемом способе реализуется, например, присвоение указанной строке (или столбцу) условного индекса w_m (или соответственно w_n, что означает отсутствие информации о номере строки (или соответственно столбца), содержащей ошибочный бит. При нумерации строк и столбцов каждой матрицы в диапазонах соответственно 1…M и 1…N значения индексов w_m и w_n могут быть положены, например, равными 0. В итоге выполнения соответствующей данной матрице операции 5.p будут сформированы сочетания индексов вида: pw_mn₁ и pw_mn₂ (в случае отсутствия информации о номере строки) либо pm₁w_n и pm₂w_n (в случае отсутствия информации о номере столбца).

Далее по аналогии с прототипом коды всех этих потенциально подлежащих корректировке бинарных символов при выполнении совокупности операций 7.1…7.P (изменение кодов ошибочных бинарных символов, определенных при выполнении соответствующей из операций 6.1…6.P, на дополнительные) корректируются в соответствии с наименованием этой совокупности операций. При этом коды бинарных символов тех матриц, в которых при выполнении совокупности операций 5.1…5.P не обнаружены ошибки ни в одной паре номеров строки и столбца, и, соответственно, при выполнении совокупности операций 6.1…6.P не выявлены сочетания индексов каждого потенциально подлежащего корректировке бинарного символа, при выполнении совокупности операций 7.1…7.P остаются без изменений (не корректируются).

Коды бинарных символов тех матриц, в которых при выполнении совокупности операций 5.1…5.P обнаружена ошибка в одной паре номеров строки и столбца, и, соответственно, при выполнении совокупности операций 6.1…6.P выявлено одно сочетание индексов каждого потенциально подлежащего корректировке бинарного символа, при выполнении совокупности операций 7.1…7.P корректируются аналогично прототипу (т.е. коды тех бинарных символов, позиции которых в соответствующих им матрицах определяются указанным сочетанием индексов, меняются на дополнительные).

Коды бинарных символов тех матриц, в которых при выполнении совокупности операций 5.1…5.P обнаружена ошибка более чем в одной паре номеров строки и столбца, и, соответственно, при выполнении совокупности операций 6.1…6.P выявлено более одного сочетания индексов каждого потенциально подлежащего корректировке бинарного символа, при выполнении совокупности операций 7.1…1.P корректируются также аналогично тому, как это происходит в прототипе, но с учетом меток («подсказок»), выработанных для каждой их таких матриц при выполнении операции 8. Продолжение пояснения содержания совокупности операций 7.1…7.P (т.е. пояснение принципа учета указанных меток при выполнении этой совокупности операций) ниже совмещено с описанием содержания операции 8.

Содержание операции 8 (определение символов, в которых произошли ошибки) состоит в следующем. Исходными данными для выполнения этой операции являются выявленные при выполнении совокупности операций 5.1…5.P (или, как отмечено выше, 6.1…6.P) сочетания трех индексов каждого потенциально подлежащего корректировке бинарного символа.

При ошибках (предварительного декодирования) в двух P-разрядных символах могут иметь место ошибки в двух бинарных символах одной матрицы (далее, если это не оговорено особо, речь идет именно о такой ситуации). При этом, если фактически имеют место ошибки в бинарных символах βpm₁n₂ и βpm₂n₂, то тогда в итоге выполнения операции 5.p будут определены (как содержащие ошибки) m₁-я и m₂-я строки и n₁-й и n₂-й столбцы p-й матрицы. И тогда при m₁≠m₂ и n₁≠n₂ в итоге выполнения операции 6.p в качестве общих для сочетания строк и столбцов p-й матрицы бинарных символов будут определены как символы βpm₁n₁, βpm₂n₂, в данной ситуации действительно являющиеся ошибочными, так и символы βpm₁n₂, βpm₂n₁, в данной ситуации ошибочными не являющиеся. При этом то, какая именно из этих двух пар бинарных символов содержит ошибки предварительного декодирования, декодеру заранее неизвестно.

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

В рассматриваемой ситуации (наличия двух ошибочных бинарных символов в одной и той же матрице) для корректной реализации совокупности операций 7.1…7.P этой совокупности операций надо «подсказать», какая именно пара бинарных символов (в рассмотренном выше примере это либо βpm₁n₁ и βpm₂n₂, либо βpm₁n₂ и βpm₂n₁) предварительно декодирована ошибочно. Необходимая «подсказка» формируется следующим образом.

Как отмечено выше, при ошибочно предварительно декодированном P-разрядном символе могут быть ошибки в определении от одного до всех P бит (разрядов) этого символа. При этом практически наверняка при ошибочном предварительном декодировании двух P-разрядных символов хотя бы для одного из P разрядов выполняется следующее условие: в одном из этих символов данный разряд декодирован правильно, а во втором - ошибочно. Вероятность такого события вычисляется следующим образом. При ошибочно предварительно декодированном P-разрядном символе вероятность ошибки в его конкретном разряде примерно равна 0.5. Тогда вероятность того, что некоторый разряд одного символа декодирован правильно, а этот же разряд второго символа - ошибочно, также равна η_{ош р}=0.5. При этом вероятность того, что указанное условие выполнено хотя бы в одном из P разрядов, определяется как η=1-(1-η_{ош р})^P. Так, при P=8→η=0.996, а при P=12→η=0.9998, т.е. оговоренное выше условие действительно выполняется практически наверняка.

Обозначим тот разряд, который в одном их символов (речь идет о тех двух P-разрядных символах, которые предварительно декодированы с ошибками) предварительно декодирован правильно, в во втором - с ошибкой, как p₀-й. Тогда при выполнении операции 5.p₀ будет обнаружено только одно сочетание строки и столбца, в котором обнаружена ошибка. Пусть, например, общим для этих строки столбца будет бинарный символ βp₀m₁n₁. Из того, что при появлении ошибки предварительного декодирования в некоторых P-разрядных символах ошибки в бинарных символах (являющихся элементами каждой из P матриц) имеют место только в разрядах (хотя и не обязательно во всех разрядах) указанных P-разрядных символов, следует, что из двух альтернативных пар возможных ошибочных бинарных символов (βpm₁n₁ и βpm₂n₂, либо βpm₁n₂ и βpm₂n₁) действительно ошибочной является та пара, в которую входит символ, совпадающий по паре индексов m и n с бинарным символом βp₀m₁n₁, т.е. пара символов βpm₁n₁ и βpm₂n₂.

В связи с изложенным, «подсказка» совокупности операций 7.1…7.P, обеспечивающая исправление ошибок предварительного декодирования двух P-разрядных символов, формирует следующим образом. При выполнении операции 8 осуществляется определение матрицы, содержащей только одну строку и только один столбец, в которых найдены ошибки предварительного декодирования (т.е. p₀-й матрицы). Этот поиск начинается, например, с p=1-й матрицы, и далее ее номер последовательно увеличивается до тех пор, пока не будет найдена требуемая (определяемая как p₀-я) матрица. Эта операция поиска выполняется путем подсчета в каждой матрице количества строк и столбцов, в которых обнаружены ошибки предварительного декодирования, и фиксации той матрицы, в которой (впервые с начала выполнения этой операции поиска) каждый из результатов подсчетов (т.е. и результат подсчетов указанных строк, и результат подсчетов указанных столбцов) совпадет с единицей. В этой матрице фиксируются номера строки m и столбца n, соответствующие позиции ошибочного бинарного символа. Эти два номера или индекса (mn) передаются на управляющий вход совокупности операций 7.1…7.P (на фиг. 1 это общий для них нижний вход). При выполнении совокупности операций 7.1…7.P в качестве подлежащих коррекции (т.е. замене их кодов на дополнительные) выбираются те пары бинарных символов, которые содержат в своем составе один символ с индексами m и n, совпадающими с зафиксированными в p₀-й матрице и переданными на входы совокупности операций 7.1…7.P в качестве «подсказки» (метки). Таким образом, в основу заявляемого способа положен тот эффект, что при не более чем двух ошибках предварительного кодирования блока P-разрядных символов все предварительно декодированные ошибочно бинарные символы во всех тех матрицах, где они имеются, могут находиться только в совпадающих позициях (т.е. при совпадающих парах индексов m и n).

Приведенное выше описание совокупности признаков заявляемого способа в статике совмещено с описанием принципа его действия.

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

Вариант реализации выполняемых на передающей стороне операций способа, отличающийся от описанного выше только тем, что указанные M+N P-разрядных избыточных символов формируются без образования указанных матриц (т.е. без переформатирования данных), а непосредственно на основе описанной выше обработки совокупностей одноименных разрядов подлежащих передаче M·N P-разрядных информационных символов с тем же результатом, является эквивалентным описанному выше. Аналогичное замечание справедливо и по отношению к необходимости процедуры переформатирования на приемной стороне.

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

Литература.

1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. 2-е издание. М.: Издательский дом «Вильяме». 2003.

2. Брауде-Золотарев Ю.М., Лаврентьев М.А. Способ помехоустойчивого кодирования и декодирования. Патент РФ №2214678.

3. Брауде-Золотарев Ю.М., Грибань С.В. Способ помехоустойчивого кодирования и декодирования. Патент РФ №2213416.

4. Смирнов О.В., Вергелис Н.И. Декодер с обнаружением и исправлением ошибок. Патент РФ №2370887.

5. Липкин И.А. Статистическая радиотехника. Теория информации и кодирования. М.: Вузовская книга, 2002.

6. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Вып. 28. М.: Радио и связь. 1987.

7. Хемминг Р.В. Теория кодирования и теория информации. М.: Радио и связь, 1983.

Изобретение относится к области кодирования/декодирования цифровой информации и может быть использовано в системах передачи информации. Техническим результатом является повышение достоверности передачи при обмене данными. Способ содержит представление на передающей стороне каждого блока данных, содержащего последовательность из K информационных P-разрядных символов, в виде P матриц, содержащих каждая по M строк и N столбцов, причем каждую матрицу компонуют из p-х разрядов информационных символов, добавляют к каждой матрице M+N избыточных (проверочных) бинарных символов, а на приемной стороне определяют номера строк и столбцов каждой матрицы, в которых обнаружены ошибки, определяют бинарный символ, являющийся общим для каждой из указанных строки и столбца, изменяют код этого бинарного символа на дополнительный, определяют символы, в которых произошли ошибки, причем каждый из таких символов определяется по той матрице, в которой ошибка обнаружена только в одном столбце и одной строке, а каждая из совокупности операций изменения кода каждого бинарного символа осуществляется над совокупностью бинарных символов, принадлежащих тем символам, в которых произошли ошибки. 1 ил.

Способ помехоустойчивого кодирования и декодирования цифровых данных, состоящий в представлении на передающей стороне каждого блока данных, содержащего последовательность из К информационных бинарных символов, в виде матрицы, содержащей M строк и N столбцов, и добавлении к этому блоку М+N избыточных бинарных символов, причем правило формирования каждого из M избыточных бинарных символов обеспечивает проверку на четность массива информационных бинарных символов соответствующей строки указанной матрицы, а правило формирования каждого из оставшихся N избыточных бинарных символов обеспечивает проверку на четность массива информационных бинарных символов соответствующего столбца этой матрицы, а на приемной стороне - в определении номеров строки и столбца указанной матрицы, в которых на основе проверки на четность обнаружена ошибка, определении бинарного символа, являющегося для указанных строки и столбца общим, и изменении кода этого бинарного символа на дополнительный, отличающийся тем, что количество матриц, в виде которых представляется каждый блок из К информационных Р-разрядных символов, выбирают равным разрядности каждого из этих символов, причем каждую р-ю (при р=1 …Р) из них компонуют из р-х разрядов информационных символов, указанные операции добавления избыточных символов на передающей стороне и определения номеров строки и столбца, в которых на основе проверки на четность обнаружена ошибка, а также определения бинарных символов, являющихся для указанных строки и столбца общими, и изменения кодов этих бинарных символов на дополнительные на приемной стороне выполняют для каждой из Р матриц, на передающей стороне формируют М+N Р-разрядных избыточных символов из Р совокупностей Μ+N указанных бинарных избыточных символов, а на приемной стороне реализуют представление каждого принятого блока данных в виде совокупности Р матриц, кроме того, определяют Р-разрядные символы, в которых произошли ошибки, причем каждый их таких символов определяется по той матрице, в которой ошибка обнаружена только в одном столбце и в одной строке, а каждая из совокупности операций изменения кода каждого бинарного символа осуществляется над совокупностью бинарных символов, принадлежащих тем Р-разрядным символам, в которых произошли ошибки.