Результат интеллектуальной деятельности: СПОСОБ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ИНФОРМАЦИИ НА ОСНОВЕ ЗАПРЕТА ОПРЕДЕЛЕННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДАННЫХ

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

Технически потребности в модулировании данных могут проявляться разными требованиями к данному процессу; наиболее известные примеры приходят из областей магнитной записи и передачи информации. Так, ввиду особенностей форматов модуляции сигнала, в магнитной записи возникает проблема предотвращения большого количества подряд идущих одинаковых битов в потоке данных («нулей» или «единиц»), она решается путем использования кодов 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 столбцов), состоящая из чисел a_i,j, каждое из которых равняется количеству двоичных слов длины i (i=1, 2, …, N), оканчивающихся на j-e разрешенное элементарное слово (j=1, 2, …, k). Для построения таблицы используются следующие правила:

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

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

3) В строке (m+1) столбец с номером j получается по индукции, а именно: a_m+i,j=a_m,{0|t}+a_m,{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: a_5,101=a_4,010+a_4,110 (так как если кодовое слово длины 4 оканчивается на 010 или на 110, то присоединенный бит 1 дает кодовое слово длины 5, оканчивающееся на 101). В свою очередь, a_4,010=a_3,001+a_3,101; a_4,110=a_3,011+a_3,111; что касается а_3,x, то данное значение равно единице, поскольку существует лишь одно кодовое слово длины 3, оканчивающееся на определенное элементарное слово длины 3. Таким образом, суммируя значения, получим, что a_5,101=3.

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

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

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

Выход: двоичный блок данных z длины N (z₁, z₂, … z_N).

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

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

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

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

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

6. Из последних построенных m-1 битов формируются старшие биты элементарного слова, номер которого обозначается-- за p (p₂=q₁, р₃=q₂, …, p_m=q_m-1). Бит p₁ равен нулю.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Строится элементарное слово q по следующему правилу: q₁=z_j+1, q₂=z_j+2, …, q_m=z_j+m.

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

8. Строится элементарное слово r по следующему правилу: r₁=z_j, q₂=z_j+1, …, r_m=z_j+m-1; также строится элементарное слово s=r, но s₁=0.

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

10. Если бит r₁ равен единице и элементарное слово s является разрешенным и имеет номер d в таблице разрешенных слов, то к y добавляется величина a_j+m-1,d (y=y+a_j+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). За a_i,j обозначим элемент таблицы А. Для лучшего понимания условимся записывать за c_i,j записывать величину a_i,j, если вместо числа j приводится элементарное слово, номер которого в списке разрешенных элементарных слов равен числу j (так, в примере а_3,2=c_3,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 бита результата уже построены, z₄=1, z₅=0, z₆=1, z=xxx101, где «xxx» - пока не определенные биты результата.

3. Отнимаем от числа y сумму первых трех элементов N-й строки таблицы А (y=y-a_6,1-a_6,2-a_6,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), z₃=1, z=xx1101, где «хх» - пока не определенные биты результата.

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

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

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

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

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

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

9. Переменная q получает значение 111 (q=111), z₂=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≥a_4,5 (5 - это номер разрешенного слова 011); неравенство выполняется (1≥1), следовательно младший бит p становится равным единице (р=111). Переменная q не лежит в множестве Q, следовательно, от у отнимаем значение а_4,5 (y=1-1=0).

9. Переменная q получает значение 111 (q=111), z₁=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,1+а_6,2+а_6,3=12.

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

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

6. Построим элементарное слово q: q₁=z₄, q₂=z₅, q₃=z₆ (q=101).

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

8. Построим элементарное слово r: r₁=z₃, r₂=z₄, r₃=z₅ (r=110) и слово s (s=010).

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

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

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

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

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

6. Построим элементарное слово q: q₁=z₃, q₂=z₄, q₃=z₅ (q=110).

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

8. Построим элементарное слово r: r₁=z₂, r₂=z₃, r₃=z₄ (r=111) и слово s (s=011).

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

10. Так как бит r₁ равен «единице», а слово 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: q₁=z₂, q₂=z₃, q₃=z₄ (q=111).

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

8. Построим элементарное слово r: r₁=z₁, r₂=z₂, r₃=z₃ (r=111) и слово s (s=011).

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

10. Так как бит r₁ равен «единице», а слово 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.