课题基金 / 基金详情

Analytic Information Theory, Combinatorics, and Algorithmics: The Precise Redundancy and Related Problems

Analytic Information Theory, Combinatorics, and Algorithmics: The Precise Redundancy and Related Problems
分析信息论、组合学和算法:精确冗余及相关问题
批准号:
0208709
负责人:
Wojciech Szpankowski
金额:
$21.5万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2002
资助国家:
美国
项目状态:
已结题
起止时间:
2002-08-01 至 2006-07-31

项目摘要

项目成果

Wojciech Szpankowski的其他基金

相似基金

相关文献

中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
Information theory has enjoyed over fifty years of rigorous research,development, and application.In spite of its relative maturity,new challenges arise due to novel applications and emerging theoreticaldevelopments (e.g., there is a resurgence of interest in sourcecoding in multimedia applications, molecular biology, and security).In the 1997 Shannon Lecture Jacob Zivpresented compelling arguments for ``backing off'' to a certain extentfrom first-order asymptotic analysis of informationsystems in order to predict the behavior of real systems withfinite (and often small) lengths (of sequences, files, codes,databases, etc.) One way of overcoming these difficulties is toincrease accuracy of asymptotic analysis by replacing first-orderanalyses (e.g., a leading term of the average code length)by full asymptotic expansions and moreaccurate analyses (e.g., large deviations, central limit laws).This research primarily focuses on an important aspect ofsource coding, namely, the redundancy rate problem.Recent years have seen a resurgence of interest inredundancy rates of lossless and lossy coding.We describe analytic, combinatorial and algorithmic methods thatwork hand in hand to solve this and other problems in information theory.The redundancy rate problem fora class of sources corresponds to determining the extent to whichthe actual code length exceeds the optimal code length.This problem is an ideal candidatefor second-order asymptoticssince one must look beyond the leading term of the code length,which is known to be the entropy of the source.Following Hadamard's precept we study these problems usingtechniques of complex analysis such as generating functions,Rice's formula, Mellin transform, Fourier series,sequence distributed modulo 1, saddle point methods,analytic poissonization and depoissonization, andsingularity analysis. We present new results forwell-studied problems (e.g., optimal codes for maximal redundancy,memoryless and Markovian sources) as well as novel formulations of old problems(e.g., redundancy of the class of mixing sources, redundancy ofarithmetic coding and the Lemepl-Ziv codes). Furthermore,we apply the techniques developed as a part of this studyto related problems such as prediction (based on pattern matching),random number generators, the average worst case probability ofundetected error in channel coding, pattern matching approach to(exact and approximate) run length coding, and others.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
CCF: Medium: Learning From Classical and Quantum Data: a Fourier Perspective
  • 批准号:
    2211423
  • 项目类别:
    Standard Grant
  • 资助金额:
    $120.0万
  • 财政年份:
    2022
  • 负责人:
    Wojciech Szpankowski
  • 依托单位:
CIF:Small: Towards Information Content of Dynamic Structures
  • 批准号:
    2006440
  • 项目类别:
    Standard Grant
  • 资助金额:
    $50.0万
  • 财政年份:
    2020
  • 负责人:
    Wojciech Szpankowski
  • 依托单位:
Collaborative Research: CIF: Small: Coded String Reconstruction Problems in Molecular Storage
  • 批准号:
    2007238
  • 项目类别:
    Standard Grant
  • 资助金额:
    $25.0万
  • 财政年份:
    2020
  • 负责人:
    Wojciech Szpankowski
  • 依托单位:
CIF: Small: Towards Structural Information
  • 批准号:
    1524312
  • 项目类别:
    Standard Grant
  • 资助金额:
    $49.96万
  • 财政年份:
    2015
  • 负责人:
    Wojciech Szpankowski
  • 依托单位:
国内基金
海外基金
Data-driven Recommendation System Construction of an Online Medical Platform Based on the Fusion of Information
Exploring the Intrinsic Mechanisms of CEO Turnover and Market Reaction: An Explanation Based on Information Asymmetry
  • 批准号:
    W2433169
  • 项目类别:
    外国学者研究基金项目
  • 资助金额:
    --
  • 批准年份:
    2024
  • 负责人:
    HAOFEI ZHANG
  • 依托单位:
SCIENCE CHINA Information Sciences