2015

22 декабря

Олег Мусин (ИППИ)

Теория мажоризации и обобщенная задача Томсона для кодов 

15 декабря

Вячеслав Прелов (ИППИ)

О пропускной способности некоторых каналов с многими пользователями при нулевой ошибке

8 декабря

Eitan Yaakobi

Generalized Sphere Packing Bound

This is a joint work with Arman Fazeli and Alexander Vardy from the University of California, San Diego

Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem: the problem of finding fractional transversals.

The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other error channels. This work studies this method in its most general setup. First, it is shown that if the error channel is regular and symmetric then the upper bound by this method coincides with the well-known sphere packing bound and thus is called the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. The art of finding the exact upper bound (or slightly weaker ones) is the assignment of weights to the hypergraph’s vertices in a way that they satisfy the constraints in the linear programming problem. In order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases significantly reduces the number of variables and constraints in the problem. We then apply this method on specific examples of error channels. We start with the Z channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the non-binary limited magnitude channel both for symmetric and asymmetric errors, where we focus on the single-error case. We follow up on the deletion channel, which was the original motivation of the work by Kulkarni and Kiyavash, and show how to improve upon their upper bounds for single-deletion-correcting codes. Since the deletion and grain-error channels resemble a very similar structure for a single error, we also improve upon the existing upper bounds on single-grain error-correcting codes. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case.

1 декабря

Григорий Кабатянский 

Об одной недоразломанной системе В.М.Сидельникова

24 ноября

Владимир Лебедев

Жесткость пространства Хэмминга 

10 ноября 

Алексей Фролов

Коды Рида-Маллера достигают пропускной способности двоичного стирающего канала при декодировании по максимуму апостериорной вероятности

(по работе С. Кудекара, М. Монделли, Э. Сасоглу и Р. Урбанке, 2015) 

3 ноября  

Леонид Бассалыго (ИППИ) 

Локализованные ошибки ("техническая" сторона доказательств)

27 октября    

Григорий Кабатянский

О новом алгоритме декодирования высокоскоростных кодов Рида-Маллера (по работе Амира Шпильки и др, 2015)

13 октября 

Владислав Щукин

Коды для гиперканала множественного доступа. Часть 2 ("вьетнамская") 

6 октября

Владислав Щукин

Коды для гиперканала множественного доступа

19 мая

Александр Барг (ИППИ, Univercity of Maryland)

Конструкции кодов со свойством локальности символов

12 мая 

Марат Бурнашев

Об оценках снизу для вероятности ошибки декодирования и расширение области, где функция надежности ДСК известна в точности. Часть 2

28 апреля

Григорий Кабатянский

О новых применениях  исправления ошибок в канале и синдроме

21 апреля

Марат Бурнашев

Об оценках снизу для вероятности ошибки декодирования и расширение области, где функция надежности ДСК известна в точности. Часть 1

14 апреля

Алексей Фролов

Верхняя граница минимального кодового расстояния для МПП-кодов над полем GF(q) на основе подсчета числа синдромов 

7 апреля

А. Ромащенко

Комбинаторные варианты теоремы  Вульфа--Слепяна о раздельном кодировании двух коррелированных источников

31 марта

Леонид Бассалыго (ИППИ)

Границы для кодов, исправляющих пачки ошибок

24 марта  

Владимир Гриценко (ЮФУ)

О p(x)-циркулянтах и их применении в теории кодирования

10 марта

Владимир Лебедев

Кодирование при наличии бесшумной обратной связи

3 марта

Никита Полянский (мехмат МГУ)

Почти свободные от перекрытий коды

24 февраля

Вячеслав Прелов

Склеивание вероятностных распределений и некоторые приложения

17 февраля

Илья Воробьев (мехмат МГУ)

Гипотеза Эрдеша о дизъюнктивных кодах

10 февраля

Леонид Бассалыго (ИППИ)

Граница Грея-Рэнкина (q-ичный алфавит)

3 февраля

Никита Полянский (мехмат МГУ)

Разделяющие коды

27 января

Игорь Жилин

Конструкция, кодирование и декодирование обобщённых кодов с локализацией ошибок на основе кодов Рида-Соломона 

20 января

Владислав Щукин (мехмат МГУ)

Почти дизъюнктивные коды