RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Пробл. передачи информ., 2012, том 48, выпуск 4, страницы 62–87 (Mi ppi2096)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Кодирование источников

Достижимые компромиссы между сложностью и эффективностью при сжатии данных с потерями

А. Гуптаa, С. Вердуb, Ц. Вайссманc

a Самсунг Телеком Америка, Даллас, США
b Принстонский университет, США
c Стэнфордский университет, США

Аннотация: Представлено несколько результатов об оптимальном соотношении между сложностью и эффективностью при сжатии данных с потерями. Первый из них показывает, что для источника без памяти со скоростью как функцией искажения $R(D)$ и ограниченной мерой искажения можно достичь точки $(R(D)+\gamma,D+\varepsilon)$ на кривой скорости как функции искажения при постоянном времени декодирования на символ и времени кодирования на символ, пропорциональном $(\lambda_1/\varepsilon)^{\lambda_2/\gamma^2}$, где $\lambda_1$ и $\lambda_2$ – константы, зависящие от источника. Второй результат состоит в том, что эта же точка достигается при постоянном времени декодирования и времени кодирования на символ, пропорциональном $(\rho_1/\gamma)^{\rho_2/\varepsilon^2}$. Из этих результатов вытекает, что для любой сколь угодно медленно возрастающей, но неограниченной функции $g(n)$ существует последовательность схем сжатия с потерями с длиной блока $n$, сложностью кодирования $O(ng(n))$ и сложностью декодирования $O(n)$, асимптотически достигающая точки $(R(D),D)$ при растущей длине блока. Также показано, что если алфавит воспроизведения конечен, то для любого заданного $R$ существует универсальная схема сжатия с потерями со сложностью кодирования $O(ng(n))$ и сложностью декодирования $O(n)$, асимптотически достигающая точки $(R,D(R))$ для любого стационарного эргодического источника с искажением как функцией скорости $D(\cdot)$.

Полный текст: PDF файл (1709 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Problems of Information Transmission, 2012, 48:4, 352–375

Реферативные базы данных:

Тип публикации: Статья
УДК: 621.391.1
Поступила в редакцию: 18.01.2011
После переработки: 10.11.2011

Образец цитирования: А. Гупта, С. Верду, Ц. Вайссман, “Достижимые компромиссы между сложностью и эффективностью при сжатии данных с потерями”, Пробл. передачи информ., 48:4 (2012), 62–87; Problems Inform. Transmission, 48:4 (2012), 352–375

Цитирование в формате AMSBIB
\RBibitem{GupVerWei12}
\by А.~Гупта, С.~Верду, Ц.~Вайссман
\paper Достижимые компромиссы между сложностью и эффективностью при сжатии данных с~потерями
\jour Пробл. передачи информ.
\yr 2012
\vol 48
\issue 4
\pages 62--87
\mathnet{http://mi.mathnet.ru/ppi2096}
\transl
\jour Problems Inform. Transmission
\yr 2012
\vol 48
\issue 4
\pages 352--375
\crossref{https://doi.org/10.1134/S0032946012040060}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000314036400006}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ppi2096
  • http://mi.mathnet.ru/rus/ppi/v48/i4/p62

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Х. Гиоран, И. Контояннис, “Компромиссы между сложностью и сжатием при сжатии данных с потерями с помощью эффективных случайных кодовых книг и баз данных”, Пробл. передачи информ., 48:4 (2012), 88–108  mathnet; C. Gioran, I. Kontoyiannis, “Complexity-compression tradeoffs in lossy compression via efficient random codebooks and databases”, Problems Inform. Transmission, 48:4 (2012), 376–394  crossref  isi
  • Проблемы передачи информации Problems of Information Transmission
    Просмотров:
    Эта страница:148
    Полный текст:19
    Литература:17
    Первая стр.:8

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017