NDLI: Bounds on the entropy of patterns of I.I.D. sequences

Please wait, while we are loading the content...

2011 IEEE Information Theory Workshop

2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo)

2009 IEEE Information Theory Workshop on Networking and Information Theory

2007 IEEE Information Theory Workshop on Information Theory for Wireless Networks

2006 IEEE Information Theory Workshop - ITW '06 Punta del Este

IEEE Information Theory Workshop, 2005.

Proceedings of the IEEE ITSOC Information Theory Workshop 2005 on Coding and Complexity

Welcome from the co-chairs

Committee members

Table of contents

Finite-length scaling of irregular LDPC code ensembles

BEAST decoding - asymptotic complexity

Symbol-by-symbol detection of space-time coded continuous phase modulated signals over fast Rayleigh fading channels

Rate-compatible path-pruned convolutional codes and their applications on channels with insertion, deletion and substitution errors

Duality between packings and coverings of the Hamming space

Interference management via capacity-achieving codes for the deterministic broadcast channel

Fisher information matrix and hyperbolic geometry

Periodic Oppermann sequences for spread spectrum systems

Steepest descent as message passing

Bounds on the performance of sphere decoding of linear block codes

Asymptotically optimum detection for large wireless networks with fading

The multivariate merit factor of a Boolean function

Bounds on signature coding for fast frequency hopping with asynchronous access

Maximum entropy and the Edgeworth expansion

New monomial bent functions over the finite fields of odd characteristic

A finite-field transform domain construction of binary low-density parity-check codes

Correlation analysis of random number sequences based on pseudo random binary sequence generation

Capacity of M-ary 2-D RLL constraints for optical recording channels

Iterative list decoding

A new method of the codeword reception of systematic codes

Viterbi algorithm motives in turbo decoding

On the capacity of erasure relay channel: multi-relay case

A note on a decoding algorithm of codes on graphs with small loops

Computing the Levenshtein distance of a regular language

A simple element inverse jacket transform coding

Generalized signature delegation algorithm

A new trellis source encoding method and its application on joint source and channel coding

Filtering: the case for "noisier" data

Soft-in soft-out Reed-Solomon decoding using critically subsampled filterbanks

Multiuser diversity in delay-limited cellular wideband systems

A unified framework for tree search decoding: rediscovering sequential decoding

Ergodic theorems for algorithmically random sequences

The mutual information constellation

Explicit expression of the interval algorithm for random number generation based on number systems

Mutual information of non-coherent Rayleigh fading channels with Gaussian input

Finite-length analysis of a capacity-achieving ensemble for the binary erasure channel

Theoretical analysis of a zero-redundancy estimator with a finite window for memoryless source

Decoding of second order Reed-Muller codes with a large number of errors

On decoding product lattices

Boneh-Shaw fingerprinting and soft decision decoding

Interleaved Reed-Solomon codes in concatenated code designs

Achieving MIMO channel capacity using multirate layered space-time coding architectures

Design of non-systematic turbo codes for universal source controlled channel decoding

Bounds on the entropy of patterns of I.I.D. sequences

On polyalphabetic block codes

Complex M-spotty byte error control codes

Analytic algorithmics, combinatorics, and information theory

Bayesian approach to a definition of random sequences with respect to parametric models

Further results on mapping functions

Capacity loss in CDMA systems due to the constraint of scalability

Universal estimation of information measures

Universal similarity

Stopping set analysis for Hamming codes

A construction of resilient functions with satisfying synthetical cryptographic criteria

Serially concatenated continuous phase modulation with low density generator matrix codes: property, optimization and performance analysis

On performance bounds for serially concatenated codes with the general inner code and interleaver

String parsing-based similarity detection

Universal lossless data embedding without explicit compression

Construction of LDPC codes for AWGN and binary erasure channels based on finite fields

Estimation and decoding strategies for channels with abruptly changing statistics

Information Theory Workshop

Proceedings 2003 IEEE Information Theory Workshop (Cat. No.03EX674)

Proceedings of the IEEE Information Theory Workshop

Proceedings 2001 IEEE Information Theory Workshop (Cat. No.01EX494)

1998 Information Theory Workshop (Cat. No.98EX131)

Bounds on the entropy of patterns of I.I.D. sequences

Content Provider	IEEE Xplore Digital Library
Author	Shamir, G.I.
Copyright Year	2005
Description	Author affiliation: Dept. of Electr. & Comput. Eng., Utah Univ., Salt Lake, UT, USA (Shamir, G.I.)
Abstract	Bounds on the entropy of patterns of sequences generated by independently identically distributed (i.i.d.) sources are derived. A pattern is a sequence of indices that contains all consecutive integer indices in increasing order of first occurrence. If the alphabet of a source that generated a sequence is unknown, the inevitable cost of coding the unknown alphabet symbols can be exploited to create the pattern of the sequence. This pattern can in turn be compressed by itself. The bounds derived here are functions of the i.i.d. source entropy, alphabet size, and letter probabilities. It is shown that for large alphabets, the pattern entropy must decrease from the i.i.d. one. The decrease is in many cases more significant than the universal coding redundancy bounds derived in prior works. The pattern entropy is confined between two bounds that depend on the arrangement of the letter probabilities in the probability space. For very large alphabets whose size may be greater than the coded pattern length, all low probability letters are packed into one symbol. The pattern entropy is upper and lower bounded in terms of the i.i.d. entropy of the new packed alphabet. Correction terms, which are usually negligible, are provided for both upper and lower bounds.
File Size	445792
File Format	PDF
ISBN	0780394801
DOI	10.1109/ITW.2005.1531888
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-08-29
Publisher Place	New Zealand
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Entropy Gas insulated transmission lines Costs Cities and towns Data processing
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in