Способ кодирования и декодирования информации на основе запрета определенных последовательностей данных


 


Владельцы патента RU 2491716:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Новосибирский национальный исследовательский государственный университет" (Новосибирский государственный университет, НГУ) (RU)

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

 

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

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

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

1. Immink K.A.S. «A Practical Method for Approaching the Channel Capacity of Constrained Codes», IEEE Transactions on Information Theory, vol.43(5), 1997.

2. Rao V.S. et al. A Rate 2/3 Modulation Code for Suppression of Intrachannel Nonlinear Effects in High-Speed Optical Transmission, IEE Proc. Optoelectronics, 2005.

3. A. Skidin et al. The analysis of the error statistics in a 5×40 Gbit/s fibre link with hybrid amplification. Optics Communications, Vol.284(19), Pp.4695-4698, September 2011.

4. Патент США №8,049,648 «Systems and methods for constructing high-rate constrained codes», November 2011.

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

Недостатком решения №2 (V.S. Rao et al.) является частность подхода, не позволяющая работать с произвольными запрещаемыми последовательностями в блоке данных (метод удаляет из сообщения лишь сочетания двоичные 1101, 1011 и 11011). Решение №1 (Immink K.A.S.) ограничено в том, что касается применения предложенного там способа лишь к так называемым кодам RLL (run-length limited - коды, ограничивающие длину серий).

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

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

Решение №4 (патент США №8,049,648) решает задачу в общем случае, как и заявляемое решение; описываемое в патенте решение использует способ, отличный от заявляемого, который при простой и эффективной реализации дает достаточно высокую кодовую скорость в результате; недостатком способа из патента №8,049,648, является невозможность обработки больших блоков данных без потери кодовой скорости; при этом кодовая скорость способа из решения №4 меньше, чем кодовая скорость заявляемого способа кодирования.

Наиболее близким к заявленному техническому решению является решение №1 (Immink K.A.S.), в котором аналогичная задача решается концептуально схожим способом с тем, каким она решается настоящим изобретением, В ходе применения способа кодирования, описываемого в решении №1, строится таблица, содержащая числа, с помощью которых впоследствии происходит формирование выходного (закодированного) блока данных путем последовательного построения битов выходного блока данных с учетом введенных ограничений в виде запрета определенных двоичных последовательностей данных. Формирование закодированных данных происходит в зависимости от предыдущих, уже сформированных, битов данных.

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

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

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

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

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

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

Описание способа

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

Условимся записывать числа в двоичной записи в порядке возрастания значимости разрядов (то есть двоичное число «1101» в десятичной записи представляется числом 11, поскольку 11=1×1+1×2+0×4+1×8); десятичные же числа будут записываться традиционно, в порядке убывания значимости разрядов (то есть, например, 61=6×10+1). Словами далее будем обозначать последовательность двоичных символов.

Способ кодирования информации основан на точном определении количества двоичных слов заданной длины, оканчивающихся на определенное подслово. Далее подслово, служащее структурным элементом обработки информации в способе, будет называться также элементарным словом, чтобы подчеркнуть, что полслова меньшей длины в кодировании данных не участвуют. Так, двоичное слово 1101 оканчивается на подслово 101 длины 3, или на подслово 01 длины 2. Сам способ кодирования использует данные результаты и заключается в последовательном итеративном «конструировании» кодового слова бит за битом с учетом входных данных.

1. Фиксируется два параметра: битовый размер блока данных (далее - N) и битовый размер элементарного слова (далее - m).

2. Весь набор элементарных слов длины m делится на запрещенные и разрешенные (процесс деления зависит от той цели, которая ставится перед кодом; в общем случае можно запретить любые элементарные слова). Запрет элементарного слова означает, что ни одно из запрещенных элементарных слов не появится в закодированном битовом блоке размера N. Обозначим за k количество элементарных слов, которое разрешено к появлению в закодированном блоке и пронумеруем их в лексикографическом порядке.

3. Строится вспомогательная таблица А размером N×k (N строк и k столбцов), состоящая из чисел ai,j, каждое из которых равняется количеству двоичных слов длины i (i=1, 2, …, N), оканчивающихся на j-e разрешенное элементарное слово (j=1, 2, …, k). Для построения таблицы используются следующие правила:

1) Первые (m-1) строк таблицы равны нулю (ai,j=0, если i=1, 2, …, m-1);

2) Строка с номером m содержит единичные значения (ai,j=1 при i=m);

3) В строке (m+1) столбец с номером j получается по индукции, а именно: am+i,j=am,{0|t}+am,{1|t}, где значение {x|t} получается присоединением бита x слева к двоичной записи числа t. Двоичная же запись числа t является записью младших m-1 битов элементарного слова с номером j.

4) Схема п.3 применяется ко всякой строке таблицы А с номером, большим (m+1).

4. Определяется совокупность элементарных слов Q, каждое из которых q может получиться только из одного элементарного слова q' путем отбрасывания младшего бита и дополнением старшим битом от слова q. Например, если элементарное слово 0100 запрещено, то элементарное слово q=1000 будет входить во множество Q, поскольку 1000 можно получить из q'=0100 или из q'=1100, но поскольку 0100 запрещен по условию, то 1000 получается единственным образом, а значит, входит в Q.

Для иллюстрации способа построения таблицы А приведем пример нумерации последовательностей. Рассмотрим по описанной выше схеме пример со следующими параметрами: N=5, m=3 (блоки из пяти битов, длина элементарного слова равна 3, запрещено единственное элементарное слово 011). Найдем значение выражения а5,101: a5,101=a4,010+a4,110 (так как если кодовое слово длины 4 оканчивается на 010 или на 110, то присоединенный бит 1 дает кодовое слово длины 5, оканчивающееся на 101). В свою очередь, a4,010=a3,001+a3,101; a4,110=a3,011+a3,111; что касается а3,x, то данное значение равно единице, поскольку существует лишь одно кодовое слово длины 3, оканчивающееся на определенное элементарное слово длины 3. Таким образом, суммируя значения, получим, что a5,101=3.

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

Способ кодирования заключается в последовательном исполнении следующих действий:

Вход: исходный двоичный блок данных y (его численное значение должно быть меньше суммы всех элементов N-й строки кодирующей таблицы А).

Выход: двоичный блок данных z длины N (z1, z2, … zN).

1. Находится элементарное слово q, с которого начнется формирование закодированной последовательности, по следующему правилу: номер старшего элементарного слова t должен быть максимальным, при котором сумма первых (t-1) элементов N-й строки кодирующей таблицы не превысит двоичного значения числа y.

2. После нахождения первого элементарного слова, имеющего номер t (обозначим само элементарное слово за q), старшие m битов результата уже построены, они соответствуют двоичному представлению числа q(zN=qm, zN-1=qm-1, …, zN-m+1=q1).

3. От числа y отнимается число, равное сумме первых (t-1) элементов N-й строки кодирующей таблицы (y=y-aN,1-aN,2-…-aN,t-1).

4. Вводится цикловая переменная j с начальным значением N-m. На каждой итерации цикла строится бит результата с номером j (zj). Биты с номерами больше N-m уже построены на первых шагах.

5. Начало цикла: если j<1, то все биты кодового слова построены. Результат в виде слова z получен, он идет на выход. Переход к шагу 12.

6. Из последних построенных m-1 битов формируются старшие биты элементарного слова, номер которого обозначается-- за p (p2=q1, р3=q2, …, pm=qm-1). Бит p1 равен нулю.

7. Если p является запрещенным словом, то p1 присваивается единичное значение (p1=1). Переход к шагу 9.

8. Если p является разрешенным словом и выполняется неравенство y≥aN-j,p, то биту p1 присваивается единичное значение (p1=1). В этом случае, если элементарное слово q не лежит в множестве Q, порождающая процедура для которого описана выше, то от y отнимается значение aN-j,p (y=y-aN-j,p).

9. Переменной q присваивается значение p (q=p), биту zj присваивается значение p1 (zj=p1).

10. Значение j уменьшается на единицу.

11. Переход к шагу 5.

12. Завершение работы и вывод результата.

Способ декодирования заключается в получении исходной последовательности у по входной закодированной последовательности z и представляет собой следующие шаги:

Вход: двоичный блок закодированных данных z длины N (z1, z2, … zN).

Выход: двоичный блок данных y.

1. За q обозначается последнее элементарное слово в последовательности z (q1=zN-m+1, q2=zN-m+2, …, qm=zN).

2. Если данное слово является запрещенным, осуществляется переход к шагу 13.

3. Получается номер слова q в списке разрешенных слов (номер s), переменной y присваивается значение y=aN,0+aN,1+aN,2+…+aN,q-1 (начальное значение, на следующих шагах способа данное значение будет увеличиваться и на выходе способа даст результат).

4. Вводится цикловая переменная j с начальным значением N-m.

5. Начало цикла: если j<1, то результат в виде слова у получен. Переход к шагу 14.

6. Строится элементарное слово q по следующему правилу: q1=zj+1, q2=zj+2, …, qm=zj+m.

7. Если q лежит в множестве Q, значение цикловой переменной j уменьшается и осуществляется переход к шагу 4.

8. Строится элементарное слово r по следующему правилу: r1=zj, q2=zj+1, …, rm=zj+m-1; также строится элементарное слово s=r, но s1=0.

9. Если элементарное слово q или элементарное слово r является запрещенным к появлению, осуществляется переход к шагу 13.

10. Если бит r1 равен единице и элементарное слово s является разрешенным и имеет номер d в таблице разрешенных слов, то к y добавляется величина aj+m-1,d (y=y+aj+m-1,d).

11. Значение j уменьшается на единицу.

12. Переход к шагу 5.

13. Аварийное завершение: кодовое слово содержит запрещенные элементарные слова.

14. Завершение работы и вывод результата.

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

Пример осуществления заявляемого способа:

1) Выберем N=6, m=3 (закодированные блоки будут иметь длину 6 бит, элементарные запрещаемые слова имеют длину 3).

2) Выберем следующие запрещаемые элементарные слова: 001 и 010. Таким образом, k=6, а разрешенными элементарными словами будут двоичные слова 000 (1), 100 (2), 110 (3), 101 (4), 011 (5), 111 (6). В скобках указаны их номера среди разрешенных слов, они пронумерованы в порядке возрастания их десятичного значения (слово с номером 1 - это слово 000, а словом с номером 6 - слово 111).

3) Построим кодирующую таблицу А размером N×k (в данном случае 6×6). За ai,j обозначим элемент таблицы А. Для лучшего понимания условимся записывать за ci,j записывать величину ai,j, если вместо числа j приводится элементарное слово, номер которого в списке разрешенных элементарных слов равен числу j (так, в примере а3,2=c3,100, а с3,010=0, так как 010 является запрещенным элементарным словом).

4) Найдем множество элементарных слов Q, каждое из которых может получиться только из одного элементарного слова путем отбрасывания его младшего бита и дополнением старшим битом данного слова. В множество Q войдут слова 100, 101 и 011, так как каждое может быть получено из двух других слов, одно из которых запрещено. Например, 101 получается или из 010, или из 110, но 010 запрещено. Данные слова хорошо заметны при построении таблицы, так как одно из слагаемых, входящих в соответствующий расчет, всегда равно нулю.

Пример кодировании: пусть численное значение исходного двоичного блока данных у равно 14 (это соответствует введенному в способе ограничению, согласно которому численное значение блока должно быть меньше суммы N-й строки таблицы А, а сумма эта равна 21). Найдем закодированное кодовое слово, соответствующее данному номеру.

1. Находим элементарное слово q, с которого начнется формирование закодированной последовательности; данное слово будет 101, так как сумма первых трех столбцов N-й строки равна 12 и не превосходит 14, а сумма четырех столбцов превосходит, поэтому разрешенное слово 4 (101) будет первым элементарным словом результата, то есть значение t=4.

2. Старшие 3 бита результата уже построены, z4=1, z5=0, z6=1, z=xxx101, где «xxx» - пока не определенные биты результата.

3. Отнимаем от числа y сумму первых трех элементов N-й строки таблицы А (y=y-a6,1-a6,2-a6,3=y-12), то есть y примет значение 2.

4. Цикловая переменная j принимает значение 3.

5. Условие j<1 не выполняется, так как j=3.

6. Формируем слово p длины 3 из последних построенных 2 битов и младшего «нуля»: р=010.

7. Так как p является запрещенным элементарным словом, то младший бит p становится равным единице (р=110), переход на шаг 9.

9. Переменная q получает значение 110 (q=110), z3=1, z=xx1101, где «хх» - пока не определенные биты результата.

10. Уменьшаем на единицу значение j, j=2.

11. Переход к шагу 5.

5. Условие j<1 не выполняется, так как j=2.

6. Формируем слово p длины 3 из последних построенных 2 битов и младшего «нуля»: р=011.

7. Так как p не является запрещенным элементарным словом, действий не предпринимаем.

8. Так как p не является запрещенным элементарным словом, то проверяем выполнения неравенства y≥a4,5 (5 - это номер разрешенного слова 011); неравенство выполняется (2≥1), следовательно младший бит p становится равным единице (р=111). Переменная q не лежит в множестве Q, следовательно, от у отнимаем значение а4,5 (y=2-1=1).

9. Переменная q получает значение 111 (q=111), z2=1, z=x11101, где «x» - пока не определенный бит результата.

10. Уменьшаем на единицу значение j, j=1.

11. Переход к шагу 5.

5. Условие j<1 не выполняется, так как j=1.

6. Формируем слово p длины 3 из последних построенных 2 битов и младшего «нуля»: р=011.

7. Так как p не является запрещенным элементарным словом, действий не предпринимаем.

8. Так как p не является запрещенным элементарным словом, то проверяем выполнения неравенства y≥a4,5 (5 - это номер разрешенного слова 011); неравенство выполняется (1≥1), следовательно младший бит p становится равным единице (р=111). Переменная q не лежит в множестве Q, следовательно, от у отнимаем значение а4,5 (y=1-1=0).

9. Переменная q получает значение 111 (q=111), z1=1, z=111101.

10. Уменьшаем на единицу значение j, j=0.

11. Переход к шагу 5.

5. Условие j<1 выполняется, так как j=0; переход к шагу 12.

12. Завершение работы и вывод результата. Результат: z=111101.

Пример декодирования: декодируем кодовое слово z=111101. Найдем число y, соответствующее ему.

1. Обозначим за q последнее элементарное слово в z длины 3 (q=101).

2. Данное слово не является запрещенным, перехода к шагу 12 не требуется.

3. Номер разрешенного слова q равен 4 (s=4). Начальное значение y=а6,16,26,3=12.

4. Цикловая переменная j принимает значение 3.

5. Условие j<1 не выполняется, так как j=3.

6. Построим элементарное слово q: q1=z4, q2=z5, q3=z6 (q=101).

7. Слово q не лежит в множестве Q.

8. Построим элементарное слово r: r1=z3, r2=z4, r3=z5 (r=110) и слово s (s=010).

9. Элементарные слова q и r являются разрешенными.

10. Так как бит r1 равен «единице», а слово s запрещено, переходим к следующему шагу.

11. Уменьшаем на единицу значение j, j=2.

12. Переход к шагу 5.

5. Условие j<1 не выполняется, так как j=2.

6. Построим элементарное слово q: q1=z3, q2=z4, q3=z5 (q=110).

7. Слово q не лежит в множестве Q.

8. Построим элементарное слово r: r1=z2, r2=z3, r3=z4 (r=111) и слово s (s=011).

9. Элементарные слова q и r являются разрешенными.

10. Так как бит r1 равен «единице», а слово s разрешено и имеет номер 5 в таблице разрешенных слов, то к числу y добавляем значение а4,5 (y=y+а4,5=12+1=13).

11. Уменьшаем на единицу значение j, j=1.

12. Переход к шагу 5.

5. Условие j<1 не выполняется, так как j=1.

6. Построим элементарное слово q: q1=z2, q2=z3, q3=z4 (q=111).

7. Слово q не лежит в множестве Q.

8. Построим элементарное слово r: r1=z1, r2=z2, r3=z3 (r=111) и слово s (s=011).

9. Элементарные слова q и r являются разрешенными.

10. Так как бит r1 равен «единице», а слово s разрешено и имеет номер 5 в таблице разрешенных слов, то к числу y добавляем значение а3,5 (y=y+а4,5=13+1=14).

11. Уменьшаем на единицу значение j, j=0.

12. Переход к шагу 5.

5. Условие j<1 выполняется, так как j=0; переход к шагу 14.

14. Завершение работы и вывод результата. Результат: y=14.

Способ кодирования и декодирования информации на основе запрета определенных последовательностей данных, включающий построение кодовой таблицы и использование ее для выполнения преобразования двоичных блоков данных, отличающийся тем, что строят кодирующую таблицу А с размерами N×k, где N - битовый размер закодированного блока данных, k - количество элементарных слов с битовым размером m, которое разрешено к появлению в закодированном блоке; первые (m-1) строк таблицы равны нулю (ai,j=0, если i=1, 2, …, m-1), где ai,j - число, равное количеству двоичных слов длины i (i=1, 2, …, N), оканчивающихся на j-e разрешенное элементарное слово (j=1, 2, …, k); строка с номером m содержит единичные значения (ai,j=1 при i=m); в строке (m+1) столбец с номером j получают, используя строку с номером m по индукции, а именно am+1,j=am,{0|t}+am,{1|t}, где значение {x|t} получают присоединением бита x слева к двоичной записи числа t; двоичная же запись числа t является записью младших m-1 битов числа j; аналогичная схема применяется ко всякой строке таблицы А с номером, большим (m+1);
после построения таблицы осуществляют кодирование входного блока данных у (его численное значение должно быть меньше суммы всех элементов N-й строки кодирующей таблицы А), путем исполнения следующих действий:
шаг 1 - находят элементарное слово q, с которого начнется формирование закодированной последовательности, по следующему правилу: номер старшего элементарного слова t должен быть максимальным, при котором сумма первых (t-1) элементов N-й строки кодирующей таблицы не превысит двоичного значения числа y;
шаг 2 - после нахождения первого элементарного слова (q), имеющего номер t, старшие m битов результата (z) уже построены, они соответствуют двоичному представлению числа q (zN=qm, ZN-1=qm-1, …, zN-m+1=q1;
шаг 3 - от числа у отнимают число, равное сумме первых (t-1) элементов N-й строки кодирующей таблицы (y=y-aN,1-aN,2-…-aN,t-1);
шаг 4 - вводят цикловую переменную j с начальным значением (N-m), на каждой итерации цикла строят бит результата с номером j (zj), биты с номерами больше (N-m) уже построены на первых шагах;
шаг 5 - если j<1, то все биты кодового слова построены, результат в виде слова z получен, осуществляют переход к шагу 12;
шаг 6 - из последних построенных m-1 битов формируются старшие биты элементарного слова, номер которого p (p2=q1, p3=q2, …, pm=qm-1), бит p1 равен нулю;
шаг 7 - если p является запрещенным словом, то p1 присваивают единичное значение (p1=1) и осуществляют переход к шагу 9;
шаг 8 - если p является разрешенным словом и выполняется неравенство y≥aN-j,p, то биту p1 присваивают единичное значение (p1=l); в этом случае, если элементарное слово q не лежит в множестве элементарных слов Q, каждое из которых s может получиться только из одного элементарного слова s путем отбрасывания младшего бита и дополнением старшим битом от слова s, то от у отнимают значение aN-j,p (y=y-aN-j,p);
шаг 9 - переменной q присваивают значение p (q=p), биту zj присваивают значение p1 (zj=p1);
шаг 10 - значение j уменьшают на единицу;
шаг 11 - переходят к шагу 5;
шаг 12 - вывод результата в виде двоичного блока данных z длины N (z1, z2, … zn), который подлежит декодированию в исходную последовательность у путем исполнения следующих шагов:
шаг 1 - через q обозначают последнее элементарное слово в последовательности z (q1=zN-m+1, q2=zN-m+2, …, qm=zN);
шаг 2 - если данное слово является запрещенным, переходят к шагу 13;
шаг 3 - получают номер слова q в списке разрешенных слов (номер s) и присваивают переменной y значение y=aN,0+aN,1+aN,2+…+aN,s-1 (начальное значение, на следующих шагах способа данное значение будет увеличиваться и на выходе даст результат);
шаг 4 - вводят цикловую переменную j с начальным значением N-m;
шаг 5 - усли j<1, то результат в виде слова у получен, переходят к шагу 14;
шаг 6 - строят элементарное слово q по следующему правилу: q1=zj+1, q2=zj+2, …, qm=zj+m;
шаг 7 - если q лежит в множестве Q, уменьшают значение цикловой переменной j и переходят к шагу 4;
шаг 8 - строят элементарное слово r по следующему правилу: r1=zj, q2=zj+1, …, rm=zj+m-1; также строят элементарное слово s=r, но s1=0.
шаг 9 - если элементарное слово q или элементарное слово r является запрещенным к появлению, переходят к шагу 13;
шаг 10 - если бит r1 равен единице и элементарное слово s является разрешенным, то добавляют к у величину aj+m-1,d (y=y+aj+m-1,d), где d - номер разрешенного слова s в таблице разрешенных слов;
шаг 11 - значение j уменьшают на единицу;
шаг 12 - переходят к шагу 5;
шаг 13 - аварийное завершение: кодовое слово содержит запрещенные элементарные слова;
шаг 14 - вывод результата в виде числа у, двоичная запись которого представляет собой декодированный блок данных.



 

Похожие патенты:

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

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

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

Изобретение относится к области электросвязи, а именно к области криптографических устройств и способов проверки электронной цифровой подписи (ЭЦП). .

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

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

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

Изобретение относится к области вычислительной техники, предназначено для приема любого двухуровневого или трехуровневого дифференциального кодированного сигнала IX последовательного двоичного самосинхронизирующегося кода (ПДСК) с преобразованием в двухразрядный асинхронный кодированный сигнал IX(1:0) и последующим помехоустойчивым выполнением полной функции синхронизации этого сигнала с помощью входной непрерывной последовательности тактовых импульсов IC за счет помехоустойчивого формирования выходного синхронизированного кодированного сигнала ОХ(1:0), выходного синхронизирующего сигнала (синхросигнала OCX), сигнала ОХ(1:0) и выходных синхросигналов начала паузы ОРС и паузы ОРХ и может быть использовано в качестве синхронного помехоустойчивого формирователя синхронизированного кодированного сигнала ОХ(1:0) и синхросигналов OCX, ОРС, ОРХ для любого двухуровневого ПДСК, например, класса 1В2В (манчестерского по ГОСТ 26765.52-87, биимпульсного или Миллера по ГОСТ 27232-87 и т.п.) или любого трехуровневого ПДСК, например, кода RZ с возвратом к нулю по ГОСТ 18977-79.

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

Изобретение относится к области вычислительно техники, предназначено для приема входного электрического или оптического трехуровневого кодированного сигнала (ТКС) IZ последовательного двоичного самосинхронизирующегося кода (ПДСК) с преобразованием в двухразрядный асинхронный трехуровневый кодированный сигнал Z(1:0), определяющий асинхронные сигналы Z1 и Z0 соответственно информации и битовой синхронизации для последующего помехоустойчивого декодирования и синхронизации ТКС за счет формирования выходного синхронизированного сигнала OZ двухуровневого последовательного двоичного кода (ПДК) без возврата к нулю и выходных синхросигналов битовой синхронизации OCZ, паузы OPZ и начала паузы ОРС с помощью входной непрерывной последовательности тактовых импульсов IC, и может быть использовано при построении любых синхронных автоматов с памятью для помехоустойчивого ввода асинхронных данных с помощью ТКС кода RZ или высокоскоростного трехуровневого кода (ВТК), в частности, может использоваться в качестве полного помехоустойчивого синхронного декодера кода RZ с возвратом к нулю по ГОСТ 18977-79 и РТМ 1495-75.

Группа изобретений относится к вычислительной технике и связи и может быть использована в локальных вычислительных сетях и внешних запоминающих устройствах. Техническим результатом является повышение достоверности приема. Устройство содержит блок синхронизации, блок выработки тактовых импульсов, блок обнаружения ошибок, блок преобразования канального кода. 2 н. и 6 з.п. ф-лы, 7 ил.

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

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

Изобретение относится к области систем освещения и оптических приемников, и более конкретно к детектированию данных, внедренных в световой поток (выход) систем освещения. Техническим результатом является создание системы детектирования для определения данных, внедренных в световой поток источника света с невидимой модуляцией «высокой частоты», используя обычные коммерческие камеры, например камеры в мобильных телефонах или веб-камеры. Предложена система детектирования для определения повторяющейся первой последовательности из N символов, включенных в первый код, причем первый код внедрен в световой поток первого источника света системы освещения, где последовательность содержит по меньшей мере N разных кадров, и каждый кадр из по меньшей мере N разных кадров получают с общим временем экспозиции, содержащим один или более моментов экспозиции, причем в каждом из N разных кадров один или более моментов экспозиции находятся в разных временных положениях по отношению к повторяющейся первой последовательности из N символов. Система содержит камеру для получения последовательностей изображений сцены через определенные структуры открытого/закрытого состояния затвора и модуль обработки для обработки полученной последовательности изображений и определения повторяющейся последовательности из N символов. 3 н. и 12 з.п. ф-лы, 12 ил.

Изобретение относится к области электросвязи и вычислительной техники. Технический результат заключается в повышении безопасности передачи данных. В способе формируют модуль в виде битовой строки, представляющей неприводимый двоичный многочлен степени s, где s - многоразрядное двоичное число, такое, что многоразрядное двоичное число 2s-1 является простым, генерируют секретный ключ в виде двух многоразрядных двоичных чисел e и d, удовлетворяющих условию ed=1 mod Ω, где Ω=2s-1, и преобразуют сообщение М и криптограмму С как элементы конечной мультипликативной группы Г, групповой операцией которой является операция умножения двоичных многочленов по модулю неприводимого двоичного многочлена степени s и которая включает в себя двоичные многочлены, степень которых меньше многоразрядного двоичного числа s. 4 з.п. ф-лы, 4 пр.

Изобретение относится к области кодирования и декодирования. Технический результат - повышенная эффективность сжатия. Способ кодирования, содержащий получение кодов, соответствующих остаткам предсказания, полученным согласно анализу предсказания, примененному к сигналам временных последовательностей, включенным в предопределенный временной интервал входных сигналов временных последовательностей, с количеством битов, подлежащих присвоению кодам соответственно остаткам предсказания, переключаемым согласно тому, удовлетворяет ли индекс, который указывает уровень периодичности и/или стационарности, соответствующей сигналам временных последовательностей в предопределенном временном интервале или сигналам временных последовательностей в интервале перед предопределенным временным интервалом входных сигналов временных последовательностей, условию, которое указывает высокую периодичность и/или высокую стационарность, или условию, которое указывает низкую периодичность и/или низкую стационарность. 10 н. и 20 з.п. ф-лы, 8 ил.

Изобретение относится к системе управления освещением, в частности, содержащей множество источников света на основе применения видимого света (VL) и инфракрасной (IR) связи для выбора и улучшенного управления источниками света. Техническим результатом является обеспечение кодирования света, т.е. встраивания кодированной информации в световой выход источника света, которое не приводит к видимому мерцанию. Указанный технический результат достигается тем, что последовательности символов канала для управления источником света определяются из последовательностей символов источника, так что не присутствует видимого мерцания в кодированном свете, испущенном источниками света. Каждый символ источника преобразуется в составной символ канала, содержащий по меньшей мере один первый символ канала, который может быть идентичен текущему символу источника, и по меньшей мере один второй символ канала, который может быть функцией текущего символа источника и по меньшей мере одного последующего и/или предыдущего символа источника. 5 н. и 13 з.п. ф-лы, 21 ил.

Изобретение относится к области электросвязи, а именно к области криптографии. Технический результат - упрощение процедуры извлечения сообщения из криптограммы. Способ шифрования включает следующую последовательность действий: генерируют секретный ключ в виде двух простых многоразрядных двоичных чисел (МДЧ) р и q, генерируют открытый ключ в виде пары МДЧ (n, N), где n=pq и N-МДЧ, удовлетворяющее соотношениям и , формируют криптограмму C в виде тройки (А, В, D) МДЧ А, В и D путем генерации вспомогательного МДЧ R<n вычисления тройки (А, В, D) в зависимости от сообщения М, открытого ключа (n, N) и МДЧ R и восстанавливают сообщение M путем вычисления корней уравнений x3+Ax2+Bx+D=0 mod р, x3+Ax2+Bx+D=0 mod q и x3+Ax2+Bx+D=0 mod n с неизвестным x и формирования сообщения М по корню последнего из указанных уравнений. В частном случае формируют криптограмму C путем генерации первого дополнительного МДЧ T<n, генерации вспомогательного МДЧ R=(Т-N) mod n, генерации второго дополнительного МДЧ U=(R2/4-N)mod n и вычисления МДЧ А, В и D по формулам A=(T-N-M)mod n, B=(U-MR) mod n и D=-MU mod n. 2 з.п. ф-лы.
Наверх