Algorithms for Q-ary Error-Correcting Codes with Feedback
Prof. Vladimir Lebedev
Institute for Information Transmission Problems in Moscow
A famous problem in Coding Theory consists in finding good bounds for the maximal size M(n,t,q) of a t-error correcting code over a q-ary alphabet Q={0,1,... ,q-1} with block length n.
This code concept is suited for communication over a q-ary channel with input alphabet X=Q and output alphabet Y=Q, where a word of length n sent by the encoder is changed by the channel in at most t letters. Here neither the encoder nor the decoder knows in advance where the errors, that is changes of letters, occur. Suppose now that having sent letters x_1,... ,x_{j-1} in X the encoder knows the letters y_1,... ,y_{j-1} in Y received before he sends the next letter x_j (j=1,2,...,n). We then have the presence of a
noiseless feedback channel. It is still an unsolved problem to determine the capacity-error-function if q> 2. We are introducing new algorithms to improve the lower bound. We also look at the case when feedback is only partially available.
Vladimir Lebedev received the M.S. in Mathematics degree in mathematics from the Lomonosov State University, Moscow, Russia, in 1987, and the Ph.D. in Mathematics degree from the Moscow Institute of Electronics and Mathematics, Moscow, Russia, in 1996. Since 1996 he is Associate Professor at the Institute for Information Transmission Problems in Moscow. He was co-organizer of severals "Workshop on Algebraic and Combinatorial Coding Theory (ACC)" in Bulgaria and Russia. His main research activities are the development of non-adaptive group testing theory, the development of coding theory with feedback and the investigations of adaptive and non-adaptive combinatorial search models.