On List Decoding Transitive Codes From Random Errors

02/01/2022
by   Anup Rao, et al.
0

We study the error resilience of transitive linear codes over 𝔽_2. We give tight bounds on the weight distribution of every such code C, and we show how these bounds can be used to infer bounds on the error rates that C can tolerate on the binary symmetric channel. Using this connection, we show that every transitive code can be list-decoded from random errors. As an application, our results imply list-decoding bounds for Reed-Muller codes even when the rate exceeds the channel capacity.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset