Cyclic Properties And Coding Speed Optimization Of The Fletcher Checksum

With the rapid development of modern wireless communication technology,dig-ital signal has gradually replaced analog signal as the main transmission signal type.Due to the complex characteristics of the channel,when the modulated signal is trans-mitted in the channel,it must be affected by the channel.In order to meet the increasing demand for efficient and reliable digital transmission and storage system,the technol-ogy(channel coding)of enhancing data anti-interference ability and improving system stability has been proposed.In this thesis,we will introduce a location dependent checksum algorithm:Fletcher checksum(FC).This algorithm is similar to the error detection ability of cyclic redun-dancy check(CRC),but it has less computation.CRC is based on polynomial division,which has a large amount of computation for modern computers.However,FC only needs to use addition,which greatly reduces the amount of calculation.Although FC and its variants are widely used,people know little about the mathematical structure of FC,so that the error detection ability of FC is mostly based on experimental simulation,which is difficult to analyze theoretically,What's worse,FC actually has two versions,one is Fletcher's original paper version termed as FC and the other is RFC 1146 ver-sion termed as FC-RFC.In this paper,it is proved that FC is a cyclic code obtained by introducing cyclic Fletcher code(CFC)and proving that CFC and FC are equivalent.Based on the clear algebraic structure of cyclic codes,we analyze the code length and code distance of FC,and discuss the error detection performance of FC,including sin-gle error correction,double errors detection,burst error detection and missed detection probability.At the same time,we give the mathematical relationship between CFC and FC-RFC.We also consider the implementation of FC.We propose a new computing scheme to prevent data hazards and make FC coding pipelined.In addition,this new computing scheme also supports the use of single instruction multiple data(SIMD)for further speed optimization.The simulation results show that the new scheme of CFC improves the coding speed by at least 46%compared with the old scheme of FC,and is almost three times as fast as CRC.