Fast cyclic redundancy check: utilizing linearity of cyclic redundancy check for accelerating correction of corrupted network packets
Systems and methods for correcting corrupted network packets are provided. An example method includes receiving a network packet via a communication channel. The network packet includes a payload and a Cyclic Redundancy Check (CRC) associated with the payload. The method continues with calculating a reference CRC based on the received payload and determining, based on the reference CRC and the received CRC, whether the network packet is corrupted. Based on the determination that the network packet is corrupted, the method continues with selecting a predetermined number of positions of bits in the payload of the network packet, precalculating a set of additional CRCs, and determining, based on the reference CRC and the set of additional CRCs, a combination of bit flips at the predetermined number of positions. The method also includes modifying the payload according to the combination of bit flips at the predetermined number of positions.
1. A system for correcting corrupted network packets, the system comprising:
at least one processor; and
a memory communicatively coupled to the at least one processor, the memory storing instructions executable by the at least one processor to perform a method comprising:
receiving, via a communication channel, a network packet including a payload and a cyclic redundance check (CRC) associated with the payload;
calculating a reference CRC based on the received payload;
determining, based on the reference CRC and the received CRC, that the network packet is corrupted; and
receiving a sequence of a set of sequences, which is an output of a neural packet processor, the sequence having bits of a length for a portion of the payload;
selecting a predetermined number of positions of bits in the payload of the network packet;
precalculating a set of additional CRCs, wherein an additional CRC of the set of additional CRCs is calculated based on the sequence of the set of sequences, the sequence of the set of sequences including a single non-zero bit at one of the predetermined number of positions, as well as sequential three-byte XOR operations;
determining, based on the reference CRC and the set of additional CRCs, a combination of bit flips at the predetermined number of positions, the combination of bit flips corresponding to a combination of the set of sequences such that a sum of the reference CRC and CRCs of the combination of the set of sequences matches the received CRC;
generating a modified payload according to the combination of bit flips at the predetermined number of positions; and
transmitting the network packet with the modified payload to a receiver over a wireless network.
2. The system of claim 1 , wherein the predetermined number of positions of bits in the payload is fewer than a length of the payload.
3. The system of claim 1 , wherein calculation of an additional CRC of the set of additional CRCs requires less operations than the calculation of the reference CRC.
4. The system of claim 1 , wherein the set of additional CRCs is obtained from a set of precalculated CRCs for each of the set of sequences, each of the set of sequences having a single non-zero bit position.
5. The system of claim 1 , wherein the determining the combination of bit flips includes iteratively:
selecting a test combination sequence of the set of sequences;
calculating a test sum of the reference CRC and the set of additional CRCs corresponding to the test combination sequence; and
determining whether the test sum matches the received CRC.
6. The system of claim 1 , wherein the determining the combination of bit flips includes:
generating a set of linear equations, wherein a linear equation of the set of linear equations corresponds to one of possible combinations of the set of sequences; and
solving the set of linear equations to determine the combination of the set of sequences.
7. The system of claim 6 , wherein the set of linear equations is solved by a Gaussian elimination method.
8. The system of claim 1 , wherein the predetermined number of positions of bits are selected based on at least one previous version of the payload transferred via the communication channel.
9. A method for correcting corrupted network packets, the method comprising:
receiving, via a communication channel, a network packet including a payload and a cyclic redundancy check (CRC) associated with the payload;
calculating a reference CRC based on the received payload;
determining, based on the reference CRC and the received CRC, that the network packet is corrupted;
receiving a sequence of a set of sequences, which is an output of a neural packet processor, the sequence having bits of a length for a portion of the payload;
selecting a predetermined number of positions of bits in the payload of the network packet;
precalculating a set of additional CRCs, wherein an additional CRC of the set of additional CRCs is calculated based on the sequence of the set of sequences, the sequence of the set of sequences including a single non-zero bit at one of the predetermined number of positions, as well as sequential three-byte XOR operations;
determining, based on the reference CRC and the set of additional CRCs, a combination of bit flips at the predetermined number of positions, the combination of bit flips corresponding to a combination of the set of sequences such that a sum of the reference CRC and CRCs of the combination of the set of sequences matches the received CRC;
generating a modified payload according to the combination of bit flips at the predetermined number of positions; and
transmitting the network packet with the modified payload to a receiver over a wireless network.
10. The method of claim 9 , wherein the predetermined number of positions of bits in the payload is less than a length of the payload.
11. The method of claim 9 , wherein the calculation of the additional CRC of the set of additional CRCs requires fewer operations than the calculation of the reference CRC.
12. The method of claim 9 , wherein the set of additional CRCs is obtained from a set of precalculated CRCs for each of the set of sequences, each of the set of sequences having a single non-zero bit position.
13. The method of claim 9 , wherein the determining the combination of bit flips includes iteratively:
selecting a test combination sequence of the set of sequences;
calculating a test sum of the reference CRC and the set of additional CRCs corresponding to the test combination sequence; and
determining whether the test sum matches the received CRC.
14. The method of claim 9 , wherein the determining the combination of bit flips includes:
generating a set of linear equations, wherein a linear equation of the set of linear equations corresponds to one of possible combinations of the set of sequences; and
solving the set of linear equations to determine the combination of the set of sequences.
15. The method of claim 14 , wherein the set of linear equations is solved by a Gaussian elimination method.
16. The method of claim 9 , wherein the predetermined number of positions of bits are selected based on at least one previous version of the payload transferred over the communication channel.