Collaborative Research: Complexity and Algorithms of Decoding Algebraic Codes

点击翻译按钮获取中文摘要

A signal, when transfered over a long distance, is likely to be corrupted. Error-correcting codes have been designed to solve this problem, so modern communications are possible as we see today. Algebraic codes are mathematically interesting and intriguing, and they form the backbone of coding theory and its applications. The best algorithms for many algebraic codes are very powerful but not very practical. Also, the exact decoding complexity is not well understood for these codes, including the simple but extremely important Reed-Solomon codes. The project will strive to identify the complexity of decoding algebraic codes and to design more efficient algorithms for a large class of algebraic codes.The main focus is on algebraic codes with natural parameters. The complexity results for these natural codes thus are more relevant to communication practice. It is expected that the project will lead to a number of substantial new results linking coding theory, computer sciences and mathematics. The project is also expected to develop graduate courses and train students in this cross-disciplinary research area.