A partially determined source generates, independently with certain probabilities, the symbols of a given basic alphabet and an indefinite symbol. Source coding should ensure accurate reproduction of the main characters, and undefined characters allow the replacement (additional definition) of any basic characters. Encoding is considered effective if it has a multinomial estimate of the complexity of encoding and decoding. It is asymptotically optimal if it provides an average code length asymptotically equal to the entropy of the source. Coding is universal if it does not depend on the probabilities of the source symbols. The method of effective asymptotically optimal universal coding of partially defined sources is described.
Download file
Counter downloads: 92
- Title Theoretically effective asymptotically optimal universal coding of partially defined sources
- Headline Theoretically effective asymptotically optimal universal coding of partially defined sources
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 47
- Date:
- DOI 10.17223/20710410/47/4
Keywords
недоопределённый источник, частично определённый источник, универсальное кодирование, полиномиальный метод, энтропия источника, квазиэнтропия слова, частотный класс, комбинаторная энтропия, представительное множество, underdetermined source, partial ly defined source, universal coding, polynomial method, source entropy, quasientropy of a word, frequency class, combinatorial entropy, representative setAuthors
References
Галлагер Р. Теория информации и надежная связь. М.: Сов. радио, 1974. 720 с
Шоломов Л. А. Элементы теории недоопределённой информации // Прикладная дискретная математика. Приложение. 2009. №2. С. 18-42
Шоломов Л. А. Сжатие частично определенной информации // Нелинейная динамика и управление. Вып. 4. М.: Физматлит, 2004. С. 377-396
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с
Шоломов Л. А. Энтропия системы частично определенных последовательностей с вложенными областями определения // Нелинейная динамика и управление. Вып. 3. М.: Физматлит, 2003. С. 305-320
Колмогоров А. Н. Три подхода к определению понятия «количество информации» // Проблемы передачи информации. 1965. Т. 1. №1. C.3-11
Чашкин А. В. Дискретная математика. М.: Академия, 2012. 352 с
Шеннон К. Э. Синтез двухполюсных переключательных схем // Работы по теории информации и кибернетике. М.: ИЛ, 1963. С. 59-101
Лупанов О. Б. Об одном подходе к синтезу схем - принципе локального кодирования // Проблемы кибернетики. Вып. 14. М.: Наука, 1965. С. 31-110
Нечипорук Э. И. О сложности вентильных схем, реализующих булевские матрицы с неопределенными элементами // Докл. АН СССР. 1965. Т. 163. №1. С. 40-43
Шоломов Л. А. О реализации недоопределенных булевых функций схемами из функциональных элементов // Проблемы кибернетики. Вып. 21. М.: Наука, 1969. С. 215-226
Андреев А. Е. О реализации частичных булевых функций схемами из функциональных элементов // Дискретная математика. 1989. Вып. 4. С. 36-45
Чашкин А. В. Методы вычисления частичных булевых функций // Дискретные модели в теории управляющих систем: VII Междунар. конф. М.: МАКС Пресс, 2006. С. 390-404
Шоломов Л. А. О функционалах, характеризующих сложность систем недоопределенных булевых функций // Проблемы кибернетики. Вып. 19. М.: Наука, 1967. С. 123-139
Andreev A. E., Clementi A. E. F., and Rolim J. D. P. Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs // LNCS. 1997. V. 1256. 1997. P. 177-187
Miltersen P. B. On the Shannon function for partially defined Boolean functions. http:// www.brics.dk/~bromille/Papers/index.html. 1999
Мадатян Х. А. О реализации не всюду определенных k-значных матриц заданной «густоты» вентильными схемами глубины два // Методы дискретного анализа в теории булевых функций и схем. Вып. 35. Новосибирск: ИМ СО АН, 1980. С. 71-82
Andreev A. E. Complexity of Nondeterministic Functions. BRICS report. Ser. RS-94-2. Febr. 1994. 47 p
Чашкин А. В. Вычисление недоопределенных функций // Дискретная математика и ее приложения. Сб. лекций молодежных научных школ. Вып. VI. М.: ИПМ РАН, 2011. С. 29-40
Krichevsky R. E. Occam's razor, partially specified Boolean functions, string matching, and independent sets // Information and Computation. 1994. Iss. 108. P. 158-174
Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989. 168 с
Шоломов Л. А. Кодирование частично определенных дискретных источников без памяти // Докл. АН. 2004. Т. 397. № 2. С. 178-180
Васильев Ю. Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. Т. 1. М.: Наука, 1974. С. 99-148
Крамер Г. Математические методы статистики. М.: Мир, 1975. 648 с
Theoretically effective asymptotically optimal universal coding of partially defined sources | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/4
Download full-text version
Counter downloads: 315