Guest column: error-correcting codes and expander graphs
Guest column: error-correcting codes and expander graphs
复制标题
嘉宾专栏：纠错码和扩展图
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
V. Guruswami
中科院分区：
文献类型：
--
作者：
V. Guruswami
编码理论中的核心算法问题是构造具有良好参数的显式纠错码，以及用于对消息进行编码和将有噪声的接收字解码为正确消息的快速算法。在过去的十年中，重大的新发展已经发生在这个问题上，使用基于图/组合结构，利用<i>扩展图</i>的力量。扩展图在理论计算机科学中的作用现在肯定是很好的赞赏。在这里，我们将调查一些使用扩展器在纠错码的建设亮点。
The central algorithmic problem in coding theory is the construction of explicit error-correcting codes with good parameters together with fast algorithms for encoding a message and decoding a noisy received word into the correct message. Over the last decade, significant new developments have taken place on this problem using graph-based/combinatorial constructions that exploit the power of <i>expander graphs</i>. The role of expander graphs in theoretical computer science is by now certainly well-appreciated. Here, we will survey some of the highlights of the use of expanders in constructions of error-correcting codes.