Частично определённый источник порождает независимо с некоторыми вероятностями символы заданного основного алфавита и неопределённый символ. Кодирование источника должно обеспечить точное воспроизведение основных символов, а неопределённые символы допускают замену (доопределение) любыми основными символами. Кодирование считается эффективным, если имеет полиномиальную оценку сложности кодирования и декодирования. Оно асимптотически оптимально, если обеспечивает среднюю длину кода, асимптотически равную энтропии источника. Кодирование универсально, если оно не зависит от вероятностей символов источника. Описан метод эффективного асимптотически оптимального универсального кодирования частично определённых источников.
Скачать электронную версию публикации
Загружен, раз: 90
- Title Теоретически эффективное асимптотически оптимальное универсальное кодирование частично определённых источников
- Headline Теоретически эффективное асимптотически оптимальное универсальное кодирование частично определённых источников
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 47
- Date:
- DOI 10.17223/20710410/47/4
Ключевые слова
недоопределённый источник, частично определённый источник, универсальное кодирование, полиномиальный метод, энтропия источника, квазиэнтропия слова, частотный класс, комбинаторная энтропия, представительное множество, underdetermined source, partial ly defined source, universal coding, polynomial method, source entropy, quasientropy of a word, frequency class, combinatorial entropy, representative setАвторы
Ссылки
Галлагер Р. Теория информации и надежная связь. М.: Сов. радио, 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 с
Теоретически эффективное асимптотически оптимальное универсальное кодирование частично определённых источников | Прикладная дискретная математика. 2020. № 47. DOI: 10.17223/20710410/47/4
Скачать полнотекстовую версию
Загружен, раз: 314