Information Technology and Systems 2015
An IITP RAS Interdisciplinary Conference & School
September, 7-11, Olympic Village, Sochi, Russia
ISBN: 978-5-901158-28-9

Russian | English










Troitskiy variant


Wednesday, September 9
11:30 - 13:30
Flagman 2
Session: Coding TheoryFuture Internet
Chair: Dr.Sci. Grigory Kabatiansky

Alexey Frolov
An Upper Bound on the Minimum Distance of Tail-Biting LDPC Convolutional codes Downoad paper
Abstract: The minimum distance of tail-biting low-density parity-check convolutional (TB-LDPCC) codes over GF(q) is investigated. An upper bound on the minimum distance of TB-LDPCC codes is derived. An asymptotic analysis of the new bound is done. It is shown that the bound not only improves all the known upper bounds for linear codes at high rates but at some cases lies under the Gilbert-Varshamov bound.

Grigory Kabatiansky, Stanislav Kruglik
On codes correcting constant number of errors in l1 metric Downoad paper
Abstract: We give a number-theoretical construction of codes in l1 (or modular) metric which for the case of fixed number of corrected errors have asymptotically minimal possible redundancy (the same as the corresponding Hamming bound). This construction is based on Bose-Chowla theorem from additive number theory.

Alexey Kreshchuk, Victor Zyablov
An upper bound on symbol error rate of generalized error-locator codes for symmetric channels Downoad paper
Abstract: There are some upper bounds on the frame error rate of the generalized error locator codes. The specifics of symmetric channels can be used to improve these bound and also introduce a bound on undetected error probability. We constructed these bound and derived a bound on symbol error rate from them. To do so we have investigated two kinds of symbol errors. The first kind include the errors that occur because of early exit from the decoder. The second kind includes the errors introduced by the erroneous decoding of an outer code. In this work we have introduced bounds on the rates of each of these kinds of symbol errors.

Mohamed H. Mostafa, Martin Bossert
Combinatorial Metrics and Collaborative Error/Erasure Decoding for Translational Metrics Downoad paper
Abstract: The combinatorial metric is a huge family of metrics. Metrics such as Hamming, burst and array (criss-cross or cover) metrics are special cases of this metric (translational metrics). The decoding problem in such a metric can be simplified by dividing it into smaller decoding problems in Hamming metric (being the widely used metric). This has been already done for both burst and array metrics. A general form of such simplification can be achieved through graph coloring. Although the coloring problem is NP hard, it has to be solved once per metric. For different combinatorial metrics the same coloring can be used if a certain relation is satisfied. A "novel" method of decoding in translational metrics beyond half the minimum distance using error/erasure decoders is introduced. By exploiting the properties of the metrics, we obtain a gain in the decoding radius but introduce decoding failures, however, with negligible probability.

Fedor Ivanov, Igor Zhilin, Victor Zyablov
Erasure Insertion in Generalized Error Locating Codes Downoad paper
Abstract: In this paper we propose a new method of erasures insertion in first outer code of generalized error locating (GEL) code. This method is based on estimations of probability of inner codes syndromes. These probabilities are used in a threshold obtaining algorithm. An optimization of this algorithm is also considered. Numerical results for suggested algorithm for some signal-noise ratios (SNRs) are presented. These results allow us to conclude that redundancy of first outer code can be significantly decreased (especially for low SNRs) using our proposed procedure.

Igor Zhilin, Fedor Ivanov, Victor Zyablov
Decoding GEL codes under decoding of the outer codes up to the Johnson bound Downoad paper
Abstract: В данной работе предложен алгоритм декодирования кодов с обобщенной локализацией ошибок (ОЛО-кодов), когда внутренние коды декодируются до границы минимального расстояния, а внешние - до границы Джонсона. На основании данного метода декодирования получена верхняя граница вероятности неправильного декодирования ОЛО-кода и построен алгоритм выбора избыточностей внешних кодов для заданной конструкции кода и входной и выходной вероятностей ошибки. Показано, что максимальная достижимая скорость кодов, оптимизированных для предложенного алгоритма декодирования существенно превосходит скорость кодовых конструкций, оптимизированных для декодирования до границы минимального расстояния.