A BDD-Based Method for LFSR Parellelization with Application to Fast CRC Encoding
2013 (English)In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, Vol. 21, no 5, 561-575 p.Article in journal (Refereed) Published
Galois Fields of order $2^k$, $GF(2^k)$, provide a unified theoretical framework for constructing parallel devices generating $k$ output bits per clock cycle. In this paper, we use $GF(2^k)$ for constructing Linear Feedback Shift Registers (LFSRs) for the parallel encoding of Cyclic Redundancy Check (CRC) codes.CRC codes are widely used in data communication and storage for detecting burst errors. Traditional methods for the parallel encoding of CRC are based on computing the $k$th power of the connection matrix of the LFSR. We propose an alternative method based on computing the $k$th power of the transition relation of the LFSR. We use Binary Decision Diagrams (BDDs) for representing the transition relation in a partitioned form. This allows us to bound the size of BDDs by $O(n^2)$, where $n$ is the size of the LFSR. The presented algorithm is asymptotically faster than previous algorithms for LFSR parallelization.
Place, publisher, year, edition, pages
2013. Vol. 21, no 5, 561-575 p.
CRC, LFSR, BDD
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-136753OAI: oai:DiVA.org:kth-136753DiVA: diva2:677046
Qc 201402052013-12-092013-12-092014-02-05Bibliographically approved