|
Проблемы передачи информации, 1986, том 22, выпуск 3, страницы 16–26
(Mi ppi942)
|
|
|
|
Теория информации и теория кодирования
Бесшумное кодирование комбинаторных источников, хаусдорфова размерность и колмогоровская сложность
Б. Я. Рябко
Аннотация:
Рассматривается задача бесшумного кодирования комбинаторных (невероятностных) источников. Показано, что стоимость оптимального кода равна хаусдорфовой размерности источника. Та же задача решается при алгоритмических ограничениях на код в двух постановках: кодирование и декодирование реализуются машинами Тьюринга и конечными автоматами. Для них найдены нижние границы стоимости
кода, выражаемые через колмогоровскую сложность и квазиэнтропию соответственно. Построены оптимальные коды для источников, порождаемых формальными грамматиками.
Поступила в редакцию: 15.05.1984
Образец цитирования:
Б. Я. Рябко, “Бесшумное кодирование комбинаторных источников, хаусдорфова размерность и колмогоровская сложность”, Пробл. передачи информ., 22:3 (1986), 16–26; Problems Inform. Transmission, 22:3 (1986), 170–179
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi942 https://www.mathnet.ru/rus/ppi/v22/i3/p16
|
Статистика просмотров: |
Страница аннотации: | 566 | PDF полного текста: | 247 | Первая страница: | 2 |
|