Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Barg A. — Complexity Issues in Coding Theory
Barg A. — Complexity Issues in Coding Theory



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Complexity Issues in Coding Theory

Автор: Barg A.

Аннотация:

Abstract. This paper deals with complexity issues in the theory of linear error-correcting codes. Algorithmic problems that we 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. We present a construction of codes that correct a linear fraction of errors with complexity nlogn. 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. We study separately the complexity of hard-decision and soft-decision decoding. For the hard-decision decoding case we present algorithms grouped in two classes, gradient-like decoding and information-set decoding. It turns out that this general approach is sufficient to study most if not all known general decoding methods. In the soft-decision decoding context, we 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. We also give 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 we give complete and self-contained proofs of the results.


Язык: en

Рубрика: Computer science/

Статус предметного указателя: Неизвестно

ed2k: ed2k stats

Год издания: 1997

Количество страниц: 115

Добавлена в каталог: 20.03.2007

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте