Информатика и вычислительная техника
• формат pdf
• размер 20.42 КБ
• добавлен 26 августа 2011 г.
Pages : 115
Publication Date : Oct 1997

Document Summary:

This paper deals with complexity issues in the theory of linear error-correcting codes. Algorithmic problems that this paper study are constructing good codes, encoding and decoding them. According to their complexity, problems are divided into easy, i.e., polynomial in the length n of the code, and difficult, i.e., exponential ones. The first part deals with easy problems. This paper presents a construction of codes that correct a linear fraction of errors with complexity n log n. The construction is based on well-known since the late 80ies explicit constructions of good expanding graphs. Another group of problems in this part is related to codes for non-Hamming errors, namely, erasures, defects (codes for memories with defective cells), and localized errors.

The second part, which forms the core of this paper, deals with difficult problems, first and foremost, maximum likelihood decoding of linear codes. This paper studies separately the complexity of hard-decision and soft-decision decoding. For the hard-decision decoding case this paper presents algorithms grouped in two classes, gradient-like decoding and information-set decoding. It tus out that this general approach is sufficient to study most if not all known general decoding methods. In the soft-decision decoding context, this paper first discuss possible problem settings and then implementations of decoding with reduced complexity.

The last part of the paper overviews most known NP-hard decoding problems including some recent nonapproximability results.

The supporting material includes many general properties of linear codes from well-known to rather sophisticated, and a brief discussion of models of computations and relevant settings for the study of complexity issues in coding theory. This paper also gives examples of many methods studied. Sometimes they just illustrate concepts and definitions, but sometimes capture the most essential features of the proofs and on occasion even replace them.

Generally this paper gives complete and self-contained proofs of the results.

The coverage is extended from classical algorithms up to very recent developments. This paper thoroughly study and compare different algorithms, especially those applicable to several seemingly non-related problems. This unified approach to algorithmic coding problems enables us to organize previously independent results in a self-contained part of coding theory.
Смотрите также

## Garrett P. The Mathematics of Coding Theory

• формат pdf
• размер 13.53 МБ
• добавлен 28 февраля 2011 г.
Prentice Hall, 2003. - 398 pages. This book makes a very accessible introduction to a very important contemporary application of number theory, abstract algebra, and probability. It contains numerous computational examples throughout, giving learners the opportunity to apply, practice, and check their understanding of key concepts. KEY TOPICS Coverage starts from scratch in treating probability, entropy, compression, Shannon's theorems, cyclic...

## Gray R.M. Entropy and Information Theory

• формат pdf
• размер 2.58 МБ
• добавлен 07 апреля 2011 г.
2nd Edition Springer, 2011. 409 p. ISBN:1441979697 This book is an updated version of the information theory classic, first published in 1990. About one-third of the book is devoted to Shannon source and channel coding theorems; the remainder addresses sources, channels, and codes and on information and distortion measures and their properties. New in this edition: Expanded treatment of stationary or sliding-block codes and their relations to...

## Hamming R.W. Coding and Information Theory

• формат djvu
• размер 1.71 МБ
• добавлен 17 апреля 2011 г.
Prentice Hall, 1986. - 272 pages. Preface to the First Edition: This book combines the fields of coding and information theory in a natural way. They are both theories about the representation of abstract symbols. The two fields are now each so vast that only the elements can be presented in a short book. Information theory is usually thought of as "sending information from here to there" (transmission of information), but this is exactly the...

## Joyner D., Kim J.-L. Selected Unsolved Problems in Coding Theory

• формат pdf
• размер 1.54 МБ
• добавлен 15 октября 2011 г.
Birkhauser Boston, 2011. - 260 pages. Using an original mode of presentation, and emphasizing the computational nature of the subject, this book explores a number of the unsolved problems that still exist in coding theory. A well-established and highly relevant branch of mathematics, the theory of error-correcting codes is concerned with reliably transmitting data over a ‘noisy’ channel. Despite frequent use in a range of contexts, the subject...

## Kabatiansky G., Krouk E., Semenov S. Error Correcting Coding and Security for Data Networks. Analysis of the Superchannel Concept

• формат pdf
• размер 2.82 МБ
• добавлен 28 октября 2011 г.
Издательство John Wiley, 2005, -290 pp. This book provides a systematic approach to the problems involved in the application of error-correcting codes in data networks. Over the last two decades the importance of coding theory has become apparent. Thirty years ago developers of communication systems considered error-correcting coding to be somewhat exotic. It was considered as an area of interest only for mathematical engineers or mathematicians...

## Ling S., Xing C. Coding Theory: A First Course

• формат pdf
• размер 1.25 МБ
• добавлен 17 апреля 2011 г.
Cambridge University Press, 2004. - 236 pages. Concerned with successfully transmitting data through a noisy channel, coding theory can be applied to electronic engineering and communications. Based on the authors' extensive teaching experience, this text provides a completely modern and accessible course on the subject. It includes sections on linear programming and decoding methods essential for contemporary mathematics. Numerous examples and...

## Micheloni R., Marelli A., Ravasio R. Error Correction Codes for Non-Volatile Memories

• формат pdf
• размер 6.38 МБ
• добавлен 02 марта 2011 г.
Springer, 2008. 337 р. ISBN: 978-1-4020-8390-7 (на английском языке) Contents Preface Acknowledgements Basic coding theory Error correction codes NOR Flash memories NAND Flash memories Reliability of floating gate memories Hardware implementation of Galois field operators Hamming code for Flash memories Cyclic codes for non volatile storage BCH hardware implementation in NAND Flash memories Erasure technique Appendix A: Hamming code...

## Neubauer A., Freudenberger J., Kuhn V. Coding theory: algorithms, architectures and applications

• формат pdf
• размер 1.83 МБ
• добавлен 07 сентября 2011 г.
The present book provides a concise overview of channel coding theory and practice as well as the accompanying algorithms, architectures and applications. The selection of the topics presented in this book is oriented towards those subjects that are relevant for information and communication systems in use today or in the near future. The focus is on those aspects of coding theory that are important for the understanding of these systems. This bo...

## Thomas M. Cover, Joy A. Thomas. Elements of information theory

• формат pdf
• размер 10.09 МБ
• добавлен 01 декабря 2009 г.
2nd ed. John Wiley & Sons, Inc. This book has arisen from over ten years of lectures in a two-quarter sequence of a senior and first-year graduate-level course in information theory, and is intended as an introduction to information theory for students of communication theory, computer science, and statistics. The first quarter might cover Chapters 1 to 9, which includes the asymptotic equipartition property, data compression, and channel...

## Wiegand T., Schwarz H. Source Coding: Part I of Fundamentals of Source and Video Coding

• формат pdf
• размер 2.9 МБ
• добавлен 09 августа 2011 г.
Из серии Foundations and Trends in Signal Processing издательства NOWPress, 2010, -224 pp. Изложение современных подходов к кодированию информации. Digital media technologies have become an integral part of the way we create, communicate, and consume information. At the core of these technologies are source coding methods that are described in this monograph. Based on the fundamentals of information and rate distortion theory, the most relevant...