On the dependency between the code symmetries and the decoding efficiency

Ivanov, KirillUrbanke, Ruediger2021-12-182021-12-182021-12-182020-01-01https://infoscience.epfl.ch/handle/20.500.14299/183838WOS:000714960300040A framework of monomial codes is considered, which includes linear codes generated by the evaluation of certain monomials. Polar and Reed-Muller codes are the two best-known representatives of such codes and can be considered as two extreme cases. Reed-Muller codes have a large automorphism group but their low-complexity maximum likelihood decoding still remains an open problem. On the other hand, polar codes have much less symmetries but admit the efficient near-ML decoding.We study the dependency between the code symmetries and the decoding efficiency. We introduce a new family of codes, partially symmetric monomial codes. These codes have a smaller group of symmetries than the Reed-Muller codes and are in this sense "between" RM and polar codes. A lower bound on their parameters is introduced along with the explicit construction which achieves it. Structural properties of these codes are demonstrated and it is shown that they often have a recursive structure.Computer Science, Information SystemsComputer Science, Theory & MethodsComputer ScienceOn the dependency between the code symmetries and the decoding efficiencytext::conference output::conference proceedings::conference paper