681_Trofimov_V.K._Teoremy_kodirovanija_neravnoznachnymi_
.pdf
|
|
|
|
|
|
|
1 |
|
|
p w l (k0 ) (w0 ), |
tY |
|
H ( ) |
|
|
|
|||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
C tY |
|
|
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
N w X N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
1 |
p w |
|
|
|
|
|
|
|
|
|
(k |
|
1)2 |
|
|
|
|
l ( k ) (w), |
|
|
l ( k0 ) (w0 ), |
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
tY |
tY |
|
|
|||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
log 1 |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
N w X |
N |
|
|
|
|
|
|
|
k k0 |
|
(k 1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T * C log 2log(k |
|
1) |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(7.2) |
||||
Так как при любых w X N выполняется неравенство |
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
log 1 (k0 1) |
|
2 l |
|
|
|
(w),tY l |
|
|
(w0 ),tY |
0 , |
|
|
|||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
( k ) |
|
|
|
|
|
|
|
|
|
|
( k0 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
k0 (k 1) |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
то из (7.2) получаем: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
r(N, , , |
|
|
|
) r(N , , (k0 ) , |
|
) |
2log k0 |
1 |
|
T ** |
. |
|
|
|
(7.3) |
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
t |
|
|
t |
|||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
Y |
|
|
|
|
|
|
|
|
|
|
|
Y |
|
|
|
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
|
|
N |
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
Из универсальной оптимальности (k0 ) |
для множества источников k |
из |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
(7.3) имеем |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
r(N, , , |
|
|
) r(N, , (k0 ) , |
|
|
) |
2log k0 1 |
|
T *** |
, |
|
|||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
t |
|
t |
|
(7.4) |
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Y |
|
|
|
|
|
|
|
|
|
N |
|
|
|
N |
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
где T *** |
не |
зависит ни |
|
от N, |
ни |
от k, ни от |
|
k0. Из (5.4) и определения |
|||||||||||||||||||||||||||||||||||||||||||||||||
R N , k |
, |
|
следует утверждение леммы. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
tY |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Лемма доказана. |
|
||||||||||||||||||||||||||||||||||||||||
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Следует отметить, что предложенное кодирование φ не требует пере-
стройки в зависимости от выбранного источника: оно само автоматически под-
страивается по выбранному источнику.
7.2.Универсальное кодирование для объединения множеств марковских источников
Пусть k , где k – марковские источники с конечной памятью s(k),
k
k =1,2,… .Имеет место следующее утверждение.
71
Теорема 7.2.1. Для множества марковских источников |
k суще- |
|
k |
ствует такое кодирование φ, что для любого источника k0 , где k0 произ-
вольное, выполняется асимптотическое неравенство
|
|
|
k s(k0 ) (k 1) |
|
2log k |
C |
|
r(N, , , tY ) |
|
log N |
0 |
|
. |
||
2N |
N |
|
|||||
|
|
|
|
|
|
||
Доказательство. Выше построен оптимальный метод кодирования мар-
ковских источников с конечной памятью. Этот метод кодирования позволяет получить для марковских источников связанности s оценку вида
R(N, |
, |
) |
k s (k 1) |
log N |
T |
, |
(7.4) |
||
|
|
|
|
||||||
s |
Y |
|
2NC tY |
|
N |
|
|
||
|
|
|
|
|
|
||||
которую асимптотически нельзя улучшить. Пусть φs– кодирование, оптималь-
ное для множества марковских источников связанности s. Каждому слову u оно ставит в соответствие слово φs(u), имеющее длительность |φs(u)|:
s (u) log ps (u) T * ,
где ps (u) – средняя вероятность слова u по множеству источников s , при условии, что на s задано КТ-распределение. Для множества источников определена средняя вероятность слова u по формуле
|
6 |
|
|
1 |
|
|
p(u) |
|
|
ps(k ) (u) . |
(7.5) |
||
2 |
|
|
||||
|
k 1 |
k 2 |
|
|||
|
|
|
|
|
|
|
Очевидно, что если объединение состоит из бесконечного числа источни- |
||||||
ков, то p(u) 1; в противном случае, |
|
p(u) 1. Построим разделимое |
||||
u X N |
|
|
u X N |
|
||
кодирование, как это сделано ранее, используя распределение (7.5), тогда коди-
рование φ имеет для слова u длительность
|
(u) |
|
log p(u) T ** . |
(7.6) |
|
|
В (7.6) T ** – равномерно ограниченная постоянная. Оценим для построенного кодирования r(N, , , tY ) . Пусть s(k0 ) по определению имеем:
72
|
|
|
1 |
p (u) ( log ps(k0 ) (u)) |
H ( ) |
|
|
|
T ** |
|
||
r(N, , , tY ) |
|
|
|
|
|
|
|
. |
(7.7) |
|||
|
|
|
|
|
||||||||
|
|
|
||||||||||
|
|
|
N u X N |
log 0 (tY ) |
|
N |
|
|||||
Согласно (7.5), (7.6) из (7.7) следует
r(N , , , |
|
) |
1 |
p (u) ( log ps(k0 ) (u)) |
|
H ( ) |
|
|
|||||||||||||
tY |
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|||||||||||||||
|
log 0 (tY ) |
|
|||||||||||||||||||
|
|
|
|
|
|
|
N u X N |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
(7.8) |
|
|
|
|
|
|
|
|
2 |
|
ps(k ) (u) |
|
|
*** |
|
|
|
|
|
|||
|
|
1 |
p (u) log 1 |
|
k0 |
|
|
|
T |
|
. |
|
|
|
|
||||||
|
2 |
|
|
|
|
|
|
|
|||||||||||||
|
|
N u X |
N |
|
|
k k0 k |
|
|
|
|
N |
|
|
||||||||
|
|
|
|
|
|
|
ps(k0 ) (u) |
|
|
|
|||||||||||
Так как
|
1 |
p (u) ( log ps(k0 ) (u)) |
|
H ( ) |
|
r N, , s(k0 ) , |
|
|
|
|
T |
R N, s(k0 ) , |
|
|
T |
||||||||||||||||||||||||
|
|
|
tY |
tY |
|||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
N |
N |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
|
N u X N |
|
|
log 0 (tY ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
(T равномерно ограничена) и |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
ps(k ) (u) |
|
|
|
|
|
|
|
||||||||||||||
|
|
|
p (u) log 1 |
|
k0 |
|
|
0 , |
|
||||||||||||||||||||||||||||||
|
|
N |
k 2 |
p |
|
|
(u) |
|
|||||||||||||||||||||||||||||||
|
|
|
u X |
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k k0 |
|
|
s(k0 ) |
|
|
|
|
|
|
|
|
|
|
||||||||||||
то из (7.8) получаем: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
r(N, , , |
|
|
) R(N, |
|
|
|
|
|
, |
|
|
) |
T |
. |
|
|
|
|
|
||||||||||||||||
|
|
|
|
t |
s(k0 ) |
t |
|
|
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
Y |
|
|
|
|
|
|
Y |
|
|
|
N |
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k s (k 1) |
|
|
|
T |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Отсюда и из (7.4) имеем r(N, , , t |
) |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
Y |
|
|
2NC(tY ) |
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Теорема доказана.
Предложенное выше кодирование целесообразно применять в том случае,
когда избыточность кодирования одного класса источников существенно отли-
чается от избыточности другого класса источников.
Например, известно, что кодируемый источник может быть либо бернул-
лиевским, либо марковским связанности s = 20. Если кодировать все источники как марковские источники с памятью s = 20, избыточность такого кодирования
будет асимптотически равна |
k 20 |
(k 1) |
log N , а кодирование, предложенное в |
||
|
|
|
|
||
|
2NC( |
tY |
) |
|
|
настоящей работе, имеет эту избыточность только для марковских источников с
73
памятью s = 20, для бернуллиевских источников это же самое кодирование бу-
дет давать избыточность |
k 1 |
log |
N L |
, что в k 20 |
раз меньше. |
||
|
|
|
L 1 |
||||
|
2NC( |
t |
) |
|
|
|
|
|
|
Y |
|
|
|
|
|
Литература
[1]Галлагер, Р. Г. Теория информации и надежная связь [Текст] / Р. Г. Галлагер. – М.: Советское радио, 1974.
[2]Колмогоров, А.Н. Три подхода к определению понятия количество информации [Текст] / А.Н. Колмогоров //Проблемы передачи информации. 1966.
–Т. 1, 1. – С. 3-11.
[3]Кричевский, Р.Е. Связь между избыточностью кодирования и достоверностью сведений об источнике [Текст]/ Р.Е. Кричевский. // Проблемы передачи информации. 1968. – Т. 4. 3. С. 48-57.
[4]Кричевский, Р.Е. Длина блока, необходимая для получения заданной избыточности [Текст] / Р.Е. Кричевский. // Доклад АНСССР. 1966. Т. 171, № 1.
[5]Кричевский, Р. Е. Оптимальное кодирование источника на основе наблюдений [Текст] / Р. Е. Кричевский. // Проблемы передачи информации. 1975.
–Т. 11. № 4. – С. 37-42.
[6]Кричевский, Р. Е. Универсальное кодирование и колмогоровская сложность [Текст] / Р.Е. Кричевский. // Тр. V Междунар. симпоз. по теор. информ.: Тез. докл. Москва Тбилиси, 1979. – Ч. 2. – С. 22-25.
[7]Кричевский, Р.Е. Сжатие и поиск информации [Текст]/ Р.Е. Кричевский. – М.: Радио и связь, 1989.
[8]Марков, А.А. Введение в теорию кодирования [Текст] / А.А. Марков. – М.: Наука, 1982.
[9]Потапов, В.Н. Оценки избыточности кодирования последовательностей алгоритмом Лемпела Зива [Текст] / В.Н. Потапов. // Дискрет. анализ и исслед. операций., Сер. 1., 1999. – Т. 6. № 2. – С. 70-81.
[10]Потапов, В.Н. Обзор методов неискажающего кодирования дискретных источников [Текст] / В.Н. Потапов. // Дискрет. анализ и исслед. операций., Сер. 1., 1999. – Т. 6. № 4.– C. 49-91.
[11]Потапов, В.Н. Теория информации. Кодирование дискретных вероятностных источников [Текст] / В.Н. Потапов. – Новосибирск: Изд. центр НГУ,
1999.
74
[12]Потапов, В.Н. Арифметическое кодирование вероятностных источников [Текст] / В.Н. Потапов. // Дискретная математика и е приложения: Сб. лекций молодежных научных школ по дискретной математике и е приложениям II. – М.: Изд-во центра прикладных исследований при ММФ МГУ, 2001. – С. 59 70.
[13]Рябко, Б.Я. Кодирование источника с неизвестными, но упорядоченными вероятностями [Текст] / Б.Я. Рябко.// Пробл. передачи информ. 1979. – Т.
15. № 2. – C. 71 77.
[14]Рябко, Б.Я. Универсальное кодирование компактов [Текст] / Б.Я. Рябко. // Доклад АН СССР. 1980. – Т. 252. № 6. – C. 1325 1328.
[15]Рябко, Б. Я. Дважды универсальное кодирование [Текст] / Б.Я. Рябко. // Проблемы передачи информации. 1984. – Т. 20, № 3. – С. 24-28.
[16]Рябко, Б. Я. Эффективный метод кодирования источников информации, использующий алгоритм быстрого умножения [Текст] / Б.Я. Рябко. // Проблемы передачи информации. 1995. – Т. 31. № 1. – С. 3-12.
[17]Рябко, Б.Я. Эффективный метод арифметического кодирования для источников с большими алфавитами [Текст] / Б.Я. Рябко, А.Н. Фионов. // Проблемы передачи информации. 1999. – Т. 35. № 4. – C. 95 108.
[18]Тарасенко, Ф.П. Введение в курс теории информации [Текст] / Ф.П. Тарасенко. – Томск: ТГУ, 1963.
[19]Трофимов, В. К. Избыточность универсального кодирования произвольных марковских источников [Текст] / В.К. Трофимов. // Проблемы передачи информации. 1974. – Т. 10. № 4. – С. 16-24.
[20]Трофимов, В. К. Универсальное равномерное по выходу кодирование бернуллиевских источников [Текст] / В.К. Трофимов. // Методы дискретного анализа в теории кодов и схем: Сб. науч. тр. – Новосибирск: Ин-т математики СО АН СССР, 1976. – Вып. 29. – С. 3-11.
[21]Трофимов, В. К. Слабоуниверсальное равномерное по выходу кодирование дискретных стационарных источников [Текст] / В.К. Трофимов. // Вестник СибГУТИ. 2010. № 2. – С. 101-111.
[22]Фано, Р. Передача информации. Статистическая теория связи [Текст] / Р. Фано. // Мир, М.: 1965.
[23]Фитингоф, Б. М. Оптимальное кодирование при неизвестной и меняющейся статистике сообщений [Текст] / Б.М. Фитингоф. // Проблемы передачи информации. 1966. –Т. 2. № 2. – С. 3 11.
75
[24]Фитингоф, Б. М. Сжатие дискретной информации [Текст] / Б.М. Фитингоф. // Проблемы передачи информации. 1967. – Т. 3. 3. – С. 28 36.
[25]Чисар, И. О каналах без шума [Текст] / И. Чисар. // Проблемы передачи информации. 1970.– Т. 6. № 4. С. 3-15.
[26]Чисар, И. Теория информации. Теоремы кодирования для дискретных систем без памяти [Текст] / И. Чисар, Я. Кернер. // М.: Мир, 1985.
[27]Хаффман, Д.А. Метод построения кодов с минимальной избыточностью [Текст]: Пер. с англ. / Д.А. Хаффман. // Кибернетический сборник. М.: ИЛ, 1961. Вып. 3. С. 79 87.
[28]Шеннон, К. Математическая теория связи [Текст] / К. Шеннон.// Работы по теории информации и кибернетике. М.: Ил, 1963. С. 243 332.
[29]Штарьков, Ю.М. Кодирование сообщений конечной длины на выходе источника с неизвестной статистикой [Текст] / Ю.М. Штарьков. // Материалы V конф. по теории кодирования и передачи информации. Москва – Горький. 1972. Ч. 1. – С. 147-152.
[30]Штарьков, Ю.М. Обобщенные коды Шеннона [Текст] /Ю.М. Штарьков. // Проблемы передачи информации. 1984. –Т. 20. № 3. – С. 3–16.
[31]Штарьков, Ю. М. Оптимальное универсальное кодирование по критерию максимальной индивидуальной относительной избыточности [Текст] / Ю.М. Штарьков, Ч.Дж. Чокенс, Ф.М.Дж. Виллемс. // Проблемы передачи информации. 1997. – T. 33. № 1. – C. 21-34.
[32]Штарьков, Ю. М. Мультиалфавитное взвешенное универсальное кодирование древовидно-контекстных источников. [Текст] / Ю.М. Штарьков, Ч.Дж. Чокенс, Ф.М.Дж. Виллемс. // Проблемы передачи информации.
2004. – T. 40. № 1. С. 98–110.
[33]Abramson, N. Information theory and coding [Текст] /N. Abramson. McGrawHill, New York, 1963.
[34]Bell, Т. C. Modeling For Text Compression [Текст] / Т.C. Bell, I.H. Witten, J.G. Cleary. // ACM Computing Surveys. Dec. 1989. – V. 21. 4. P. 557-591.
[35]Burrows, M. A block-sorting lossless data compression algorithm [Текст] / M. Burrows, D.J. Wheeler // Tech. Rep. 124, Digital Systems Res. Ctr. – Palo Alto, CA, May 10. 1994.
[36]Cover, T. Enumerative source coding [Текст] / T. Cover //IEEE Trans. Inform. Theory. Jan. 1973. – V. IT–19. – P. 73-76.
76
[37]Davisson, L. D. Comments on `Sequence time coding for data compression' [Текст] / L.D. Davisson. // Proc. IEEE (Corresp.). Dec. 1966. – V. 54. – P. 2010.
[38]Davisson, L. D. Universal Noiseless Coding [Текст] / L.D. Davisson. //IEEE Trans. Inform. Theory. 1973. – V. 19. № 6. – P. 783–795.
[39]Elias, P. The e cient construction of an unbiased random sequence [Текст] / P. Elias. // Ann. of Math. Statist. 1972. – V.43. № 3. – P. 864-870.
[40]Elias, P. Interval and recency rank source encoding: two on-line adaptive varia- ble-rate schemes [Текст] / P. Elias. // IEEE Transactions on Information Theory. January 1987. – V. 33. № 1. – P. 3-10.
[41]Faller, N. An adaptive system for data compression [Текст]/ N. Faller. // in 7th Asilomar Conf. on Circuits, Systems, and Computing. 1973. – P. 593-597.
[42]Jelinek, F. Probabilistic information theory [Текст] /F. Jelinek. New York: McGraw-Hill, 1968. – P. 476–489. transmission in the case of continious signals.
[43]Jelinek, F. On variable length-to-block coding [Текст] / F. Jelinek, K. Schneider. // IEEE. Trans. Inform. Theory. Nov. 1972. – V. IT–18. – P. 765-774.
[44]Jelinek, F. Variable-length encoding of xed-rate Markov sources for xed-rate channels [Текст] / F. Jelinek, K. Schneider. // IEEE Transactions on Information Theory. – 1974. – V. 20. № 6. – P. 750 - 755.
[45]Gallager, R. G. Variation on a theme by Human [Текст]/ R. Gallager. // IEEE Transactions on Information Theory. November 1978. – V. 24. № 6. – P. 668674.
[46]Katona, G. General theory of noiseless channels [Текст] /G. Katona. // UDINE 1970. Courses and lectures – № 31. P.69.
[47]Knuth, D. E. Dynamic Hu man coding [Текст] / D. Knuth.// J. Algorithms. 1985. – V. 1985. – P. 163-180.
[48]Kraft, L.G. A device for quantizing, grouping, and coding amplitude modulated pulses [Текст] / L.G. Kraft. // Cambridge, MA: MS Thesis. – Electrical Engineering Department, Massachusetts Institute of Technology. 1949.
[49]Krichevsky, R.E. Optimal sample based encoding Markov sources [Текст] / R.E. Krichevsky, V.K. Tro mov. // Third Czechoslovak-Soviet-Hungarian seminar on information theory. – Liblice, 1980. –P. 131-138.
[50]Krichevsky, R.E. The performance of universal encoding [Текст] / R.E. Krichevsky, V.K. Tro mov. // IEEE Transactions on Information Theory. 1981.
– V. 27. № 2. – P. 199-207.
77
[51]Lynch, T. J. Sequence time coding for data compression [Текст] / T. Lynch // Proc.IEEE (Corresp.). Oct. 1966 – V. 54. – P. 1490-1491.
[52]Lynch, T. J. Data compression with error-control coding for space telemetry [Текст] / T. Lynch. Ph.D. dissertation, Univ.– Maryland, College Park, May 1966.
[53]McMillan, B. Two inequalities implied by unique decipherability [Текст] / B. McMillan. // IEEE Trans.Information Theory. 1956. – V. 2. № 4. – P. 115-116.
[54]Manstetten, D. Tight bounds on the redundancy of Human codes [Текст] / D. Manstetten. // IEEE Transactions on Information Theory. Jan. 1992. – V. 38. № 1. – P. 144-151.
[55]Rissanen, J. Generalized Kraft inequality and arithmetic coding [Текст] / J. Rissanen. // IBM J. Res. Develop. 1976. – V. 20. №. 3. – P. 198-203.
[56]Rissanen, J. Universal modelling and coding [Текст] / J. Rissanen. G. Langdon. // IEEE Trans. Inform. Theory. 1981.– V. IT–27. 1. – P. 12-23.
[57]Rissanen, J. A universal data compression system [Текст]/ J. Rissanen. // IEEE Trans. Inform. Theory. Sept. 1983. – V. IT–29. – P. 656-663.
[58]Ryabko, B. A fast on-line adaptive code [Текст] / B. Ryabko.// IEEE Trans. Inform. Theory. July 1992. – V. 38. – P. 1400-1404.
[59]Ryabko, B. Data compression by means of a book stack [Текст] / B. Ryabko. // Probl. Inform. Transm. 1980. – V. 16. – P. 265-269.
[60]Savari, S. A., Gallager, R. G. Generalized Tunstall codes for sources with memory [Текст] / S. A. Savari, R. G. Gallager // IEEE Trans. Inform. Theory. – 1997. – V. 43. № 2. – P. 658-668.
[61]Shannon, Claude E. A Mathematical Theory of Communication [Текст] / C. Shannon // Bell System Technical Journal. July/October 1948. – V. 27. № 3. – P. 379-423.
[62]Shtarkov, Y. М., Babkin, V. F. Combinatorial encoding for discrete stationary sources [Текст] / Y. М. Shtarkov, V. F. Babkin. // 1973 IEEE International Symposium on Information Theory. – Budapest, 1973. – P. 249-257.
[63]Verdu, S. Fifty Years of Shannon Theory [Текст] / S. Verdu. // IEEE Transactions on Information Theory. 1998. – V. 44. № 6. – P. 2057-2078.
[64]Vitter, J. S. Dynamic Hu man coding [Текст] / J.S. Vitter // ACM Trans. Math. Software. June 1989. – V. 15. – P. 158-167.
[65]Willems, F. M. J. The context-tree weighting method: Basic properties [Текст] / F.M.J. Willems , Y.M. Shtarkov,T.J. Tjalkens // IEEE Trans. Inform. Theory. – May 1995. – V. IT–28. – P. 653-664.
78
[66]Witten, I. H. Arithmetic coding for data compression [Текст] / I.H. Witten , R. Neal R., J.G. Cleary // Comm. of the Assoc. Сотр. Math. 1987. – V. 30. № 6. – P. 520-540.
[67]Lempel, A. A universal algorithm for sequential data compression [Текст] / J. Ziv, A. Lempel. // IEEE Transactions on Information Theory. May 1977.– V. 23. № 3. P. 337-343.
[68]Ziv, J. Compression of individual sequences via variable-rate coding [Текст] / J. Ziv, A. Lempel. // IEEE Transactions on Information Theory. Nov. 1978. – V. IT-24. No 5. – P. 530-536.
[69]Трофимов, В.К. Сжатие неравнозначными символами информации, порожденной неизвестным источником без памяти [Текст] / Т.В. Храмова, В.К. Трофимов. // Автометрия. Новосибирск, 2012. – T. 48. № 1. – C. 3044.
[70]Трофимов, В.К. Сжатие информации порожденной неизвестным источником [Текст] / Т.В. Храмова, В.К. Трофимов. // Электросвязь. – Москва,
2012. – 4. – C. 41-44.
[71]Трофимов В.К., Храмова Т.В. // Универсальное кодирование марковских источников неравнозначными символами. – Дискретный анализ и исследование операций. Новосибирск, май–июнь 2013. – Том 20, № 3. – стр. 71–83.
[72]Трофимов В.К., Храмова Т.В. // Универсальное кодирование марковских источников неравнозначными символами. – Дискретный анализ и исследование операций. Новосибирск, май–июнь 2013. – Том 20, № 3. – стр. 71–83
[73]Трофимов В.К., Храмова Т.В. // Кодирование неизвестного стационарного источника символами неравной длительности. – Ползуновский вестник. Барнаул, 2014. – № 2/1. – стр. 61-63.
[74]Трофимов В.К., Храмова Т.В.//Оптимальное универсальное кодирование для объединения различных множеств источников символами неравной длительности (статья). Вестник СибГУТИ. Новосибирск. 2014/ – № 4. – С.
30-36
79
Трофимов Виктор Куприянович
Храмова Татьяна Викторовна
ТЕОРЕМЫ КОДИРОВАНИЯ
НЕРАВНОЗНАЧНЫМИ СИМВОЛАМИ
ДЛЯ ДИСКРЕТНЫХ КАНАЛОВ БЕЗ ШУМА
МОНОГРАФИЯ
Редактор: Лыткина Д.В. Корректор: Анисенева Е.А.
Подписано в печать 30.11.2016 формат бумаги 60х84/16, отпечатано на ризографе, шрифт №10,
изд. л. – 5,1, заказ № 218, тираж – 300. Редакционно-издательский отдел СибГУТИ
630102, Новосибирск, ул. Кирова, 86, офис 107, тел.:(383) 269-82-36
80