Нумерационное кодирование двоичных последовательностей с ограничениями на длины серий, вес, заряд тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Курмаев, Олег Феатьевич

• Курмаев, Олег Феатьевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Курмаев, Олег Феатьевич

Введение

Глава 1. Кодирование последовательностей с ограниченными длинами серий.

1.1. Предисловие.

1.2. Последовательности с ограниченными длинами серий

1.3. Нумерация и денумерация.

1.4. Поразрядное уравновешивание для (с1,к,г) - последовательностей

1.5. Поразрядное уравновешивание для - последовательностей

1.6. Выводы к главе

Глава 2. Нумерационное кодирование двоичных последовательностей с ограничениями на длины серий и вес

2.1. Предисловие.

2.2. Определение числа последовательностей.

2.3. Вычисление весовых коэффициентов разрядов

2.4. Определение минимально и максимально возможного веса последовательности

2.5. Алгоритмы нумерации и денумерации

2.6. Выводы к главе

Глава 3. Двоичные последовательности с ограничениями на длины серий нулей, вес или заряд

3.1. Предисловие.

3.2. Определение количества последовательностей.

3.3. Явный метод определения числа последовательностей

3.4. Производящие функции для перечисления (¿,к,г) - последовательностей с постоянным весом или постоянным зарядом.

3.5. Алгоритмы нумерации и денумерации (с1,к,1,г) - последовательностей с постоянным весом или зарядом

3.6. Замечания к главе

3.7. Выводы к главе

Введение диссертации (часть автореферата) на тему «Нумерационное кодирование двоичных последовательностей с ограничениями на длины серий, вес, заряд»

Актуальность работы. В течение последних 30 лет мы являемся свидетелями революции в цифровой аудио и видео записи. Компакт-диск и DVD сделались предметом широкого потребления. Они стали стандартом де-факто для хранения и переноса значительных объёмов информации. Быстро растёт популярность дисковых массивов данных и сетевых хранилищ. Миллионы жёстких дисков круглосуточно вращаются в высокопроизводительных серверах, обеспечивая доступ половины населения Земли к сети Интернет. Все эти продукты массовой памяти были бы невозможны без применения передовых систем канального кодирования.

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

В 1965 г. американский специалист в области теории информации У. Каутц (W. Kautz) предложил нумерационную процедуру кодирования для канала с одним ограничением (d или к). В 1970 г. Д. Тонг (D. Tang) и JI. Бал (L. Bahl) распространили идею Каутца на кодирование канала с (d, к) - ограничениями. В 1971 г. В. Ф. Бабкин, затем в 1973 г. Т. Ковер (Т. Cover) предложили универсальную схему нумерационного кодирования для источников. Метод Бабкина и Ковера оказался чрезвычайно удачным и, благодаря усилиям таких учёных как К. Имминк (К. A. S. Immink), В. Д. Колесник, Ч. Шалкенс (Т. Tjalkens), Ф. Браун

V. Braun), позволил дополнительно ввести стыковочные ограничения (Z, г) и стал активно применяться для блокового кодирования каналов с (d,k,l,r) - ограничениями.

Этот метод дал начало многочисленным теоретическим исследованиям в области кодирования последовательностей с ограничениями. Кроме того, он позволил распространить существующие достижения, полученные для кодирования источника на кодирование канала с (d, к) -или (d,k,l,r) - ограничениями. Нумерационная техника явно показала комбинаторную природу этого канала. Она позволила получить рекуррентные уравнения и производящие функции для перечисления последовательностей с ограничениями, что в свою очередь, дало возможность изучать асимптотику и получать оценки для канала.

В инженерной практике техника нумерационного кодирования последовательностей с ограничениями, несмотря на конкуренцию альтернативных способов, позволила Имминку разработать EFM код, который лёг в основу стандартов систем компакт-диск (CD) и цифровой диск (DVD). С этого момента канальное кодирование для оптической записи базируется на нумерационном методе.

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

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

Задачи исследования. Для реализации цели диссертации нужно было решить следующие задачи:

• распространить метод нумерационного кодирования на лексикографически упорядоченные двоичные последовательности с широким классом ограничений;

• выделить и рассмотреть специальные классы ограничений, а именно:

- ограничения на длины серий и вес;

- ограничения на длины серий нулей и накопленный заряд;

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

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

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

Научная новизна. Научная новизна диссертации заключается в том, что в ней впервые:

• предложены равновесные двоичные последовательности, у которых ограничения на длины серий нулей и длины серий единиц независимы;

• получены весовые спектры кода с ограничениями на длины серий нулей и единиц, а также получены весовой и зарядовый спектры кода с ограничениями на длины серий нулей;

• найдены рекуррентные и явные формулы для определения числа двоичных последовательностей с ограничением на длины серий нулей и заряд;

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

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

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

Научные положения, выносимые на защиту. На защиту выносятся следующие положения:

• кодирование двоичных последовательностей с к, I, г) - ограничениями на длины серий нулей с линейной трудоёмкостью;

• расширение класса ограничений путём введения раздельных ограничений на длины серий нулей и единиц и добавления совместных ограничений на вес или заряд;

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

• нумерационные алгоритмы кодирования и декодирования последовательностей с ограничениями.

Апробация работы. Результаты диссертационной работы докладывались на российских и международных конференциях: 1) 7th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-7), Ban-sko, Bulgaria, June 18 - 24, 2000; 2) IEEE International Symposium on Information Theory, Lausanne, Switzerland, June 6 - July 5, 2002; 3) lOth International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-10), Zvenigorod, Russia, September 3 - 9, 2006. 4) 7th East-West Design & Test Symposium (EWDTS 2009), Moscow, Russia, September 18 - 21, 2009.

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

Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения и списка литературы из 56 наименований. Общий объём работы составляет 114 страниц. Диссертация содержит 6 рисунков и 16 таблиц общим объёмом 8 страниц.

Заключение диссертации по теме «Теоретические основы информатики», Курмаев, Олег Феатьевич

3.7. Выводы к главе 3

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

Заключение

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

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

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

3. Для (с1,к,г) - и (с1,к,1,г) - последовательностей расширен класс ограничений, а именно введены дополнительные ограничения:

• на вес;

• на накопленный заряд.

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

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

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

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

7. Разработаны алгоритмы нумерационного кодирования и декодирования исследуемых последовательностей.

Список литературы диссертационного исследования кандидат физико-математических наук Курмаев, Олег Феатьевич, 2010 год

1. К. A. S. 1.mink. Codes for Mass Data Storage Systems. 2 ed. Eindhoven, The Netherlands: Shannon Foundation Publishers, 2004.

2. K. A. S. Immink, P. H. Siegel, J. K. Wolf. Codes for digital recorders // IEEE Trans. Inf. Theory. 1998. V. 44, №. 6. P. 2260-2299.

3. К. Шеннон. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963.

4. Р. Н. Siegel. Recording codes for digital magnetic storage // IEEE Trans. Magn. 1985. V. Mag-21, №. 5. P. 1344-1349.

5. P. A. Franaszek. Sequence-state Methods for Run-length-limited Coding // IBM J. Res. Dev. 1970. V. 14, №. 4. P. 376-383.

6. P. A. Franaszek. Run-Length-Limited Variable Length Coding with Error Propagation Limitation. U.S. Patent 3,689,899, Sep. 1972.

7. T. Horiguchi, K. Morita. On optimization of modulation codes in digital recording // IEEE Trans. Magn. 1976. V. Mag-12, №. 6. P. 740-742.

8. A. M. Patel. Zero-Modulation Encoding in Magnetic Recording // IBM J. Res. Dev. 1975. V. 19, №. 4. P. 366-378.

9. D. T. Tang, L. R, Bahl. Block Codes for a Class of Constrained Noiseless Channels // Inform, and Control. 1970. V. 17, №. 5. P. 436-461.

10. G. F. M. Beenker, K. A. S. Immink. A Generalized Method For Encoding and Decoding Run-Length-Limited Binary Sequences // IEEE Trans. Inf. Theory. 1983. V. IT-29, №. 3. P. 751-754.

11. П. И. Васильев, В. Д. Колесник. Коды с ограниченными длинами серий // Помехоустойчивое кодирование и надёжность ЭВМ / Под109ред. В. В. Зяблова; Академия наук СССР, Институт проблем передачи информации. М.: Наука, 1987. С. 95-109.

12. Н. С. Ferreira. Lower bounds on the minimum Hamming distance achievable with runlength constrained or DC-free block codes and the synthesis of a (16,8) dmin = 4 DC-free block code // IEEE Trans. Magn. 1984. V. Mag-20, №. 5. P. 881-883.

13. P. Lee. Combined Error-Correcting/Modulation Recording Codes: Dr. scient. thesis / University of California. San Diego, 1988.14. 0. Ytrehus. Codes for error control: Ph.D. thesis / University of Bergen. Norway, 1989.

14. K. A. S. Abdel-Ghaffar, J. H. Weber. Bounds and constructions for runlength-limited error-control block codes // IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 3. P. 789-800.

15. P. P. Варшамов, Г. M. Тененгольц. Код, исправляющий одиночные не-симметрические ошибки // Автоматика и телемеханика. 1965. Т. 26, № 2. С. 288-292.

16. V. D. Kolesnik, V. Yu. Krachkovsky. Generating Functions and Lower Bounds on Rates for Limited Error-Correcting Codes // IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 3. P. 778-788.

17. E. Zehavi, J. K. Wolf. On Runlength Codes // IEEE Trans. Inf. Theory. 1988. V. IT-34, №. 1. P. 45-54.

18. П. И. Васильев. Блоковое кодирование с ограниченными длинами серий для систем цифровой магнитной записи: Автореф. дис. канд. техн. наук: 05.13.01 / ЛИАП. Ленинград, 1991.

19. V. I. Levenshtein, A. J. Н. Vink. Perfect (d, к)-Codes Capable of Correcting Single Peak-Shifts 11 IEEE Trans. Inf. Theory. 1993. V. IT-39, №. 2. P. 656-662.

20. V. Braun, К. A. S. Immink. An Enumerative Coding Technique for DC-Free Runlength-Limited Sequences // IEEE Trans. Commun. 2000. V. 48, №. 12. P. 2024-2031.

21. H. Nyquist. Certain topics in telegraph transmission theory // Trans. AIEE. 1928. V. 47. P. 617-644.

22. E. Gorog. Redundant alphabets with desirable frequency spectrum properties // IBM J. Res. Dev. 1968. V. 12, №. 3. P. 234-241.

23. I. C. Mallinson, I. W. Miller. Optimal codes for digital magnetic recording // Radio Elec. Eng. 1977. V. 47. P. 172-176.

24. A. Gabor. Adaptive coding for self-clocking recording // IEEE Trans. Electron. Comput. 1967. V. EC-16, №. 6. P. 866-868.

25. G. L. Pierobon. Codes for zero spectral density at zero frequency // IEEE Trans. Inf. Theory. 1984. V. IT-30, №. 2. P. 435-439.

26. K. Norris, D. S. Bloomberg. Channel capacity of charge-constrained run-length limited codes 11 IEEE Trans. Magn. 1981. V. Mag-17, №. 6. P. 3452-3455.

27. K. A. S. Immink. Properties and Constructions of binary channel codes: Ph.D. thesis / Eindhoven University of Technology. The Netherlands, 1985.

28. О. Ф. Курмаев. Кодирование последовательностей с ограниченными длинами серий // Пробл. передачи информ. 2001. Т. 37, № 3. С. 34-43.

29. В. Ф. Бабкин. Метод универсального кодирования источника независимых сообщений неэкспонендиальной трудоёмкости // Пробл. передачи информ. 1971. Т. 7, № 1. С. 13-21.

30. T. M. Cover. Enumerative source coding // IEEE Trans. Inf. Theory. 1973. V. IT-19, №. 1. P. 73-77.

31. T. J. Tjalkens. On the Principal State Method for Run-Length Limited Sequences // IEEE Trans. Inf. Theory. 1994. V. IT-40, №. 3. P. 934-941.

32. O. Kurmaev. An Algorithm for Testing Run-Length Constrained Channel Sequences // Proc. EWDTS'2009. Moscow. Russia. Sep. 18-21. 2009. P. 391-392.

33. J. P. M. Schalkwijk. An algorithm for source coding // IEEE Trans. Inf. Theory. 1972. V. IT-18, №. 3. P. 395-399.

34. D. E. Knuth. Efficient balanced codes // IEEE Trans. Inf. Theory. 1986. V. IT-32, №. 1. P. 51-53.

35. H. D. L. Hollmann, K. A. S. Immink. Performance of Efficient Balanced Codes /¡IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 3. P. 913-918.

36. K. A. S. Immink. A Practical Method for Approaching the Channel Capacity of Constrained Channels // IEEE Trans. Inf. Theory. 1997. V. IT-43, №. 5. P. 1389-1399.

37. D. A. Huffman. A Method for the Construction of Minimum-Redundancy Codes 11 Proc. IRE. 1952. V. 40. P. 1098-1101.

38. O. Kurmaev. Weight and charge distribution of binary run-length limited codes // Proceedings of Tenth International Workshop on Algebraic and Combinatorial Coding Theory. Zvenigorod, Russia. 2006. Sep. 3-9. 2006. P. 174-178.

39. Дж. Риордан. Введение в комбинаторный анализ. М.: Изд-во иностр. лит-ры, 1963.

40. О. Ф. Курмаев. Нумерационное кодирование последовательностей с ограничениями на длины серий нулей и вес // Пробл. передачи информ. 2002. Т. 38, № 4. С. 3-9.

41. Г. Сегё. Ортогональные многочлены. М.: Гос. изд-во физ.-мат. литры, 1962.

42. М. Абрамовиц, И. Стиган. Справочник по специальным функциям с формулами, графиками и математическими таблицами. М.: Наука, 1979.

43. S. Shamai, E. Zehavi. Bounds on the capacity of the bit-shift magnetic recording channel // IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 3. P. 863-872.

44. H. C. Ferreira, S. Lin. Error and Erasure Control (d, k) Block Codes // IEEE Trans. Inf. Theory. 1991. V. IT-37, №. 5. P. 1399-1408.

45. K. A. S. Immink. DC-Free Codes of Rate (n 1 )/n, n Odd // IEEE Trans. Inf. Theory. 2000. V. IT-46, №. 2. P. 633-634.

46. E. Gilbert. Synchronization of binary messages // IRE Trans. Inform. Theory. 1960. V. 6, №. 4. P. 470-477.

47. Y. Choi, W. Szpankowski. Pattern Matching in Constrained Sequences // IEEE Intl. Symposium on Information Theory (ISIT 2008). Toronto, Canada. Jul. 6-11. 2008. P. 2141-2145.

48. K. I. Kerpez, A. Gallopoulos, C. Heegard. Maximum entropy charge-constrained run-length codes // IEEE J. Sel. Areas Commun. 1992. V. SAC-10, №. 1. P. 242-253.