冗余余數(shù)系統(tǒng)低復(fù)雜度快速糾錯(cuò)算法設(shè)計(jì)
doi: 10.11999/JEIT141454
-
1.
(清華大學(xué)數(shù)學(xué)科學(xué)系 北京 100084) ②(電子科技大學(xué)通信抗干擾技術(shù)國家級重點(diǎn)實(shí)驗(yàn)室 成都 611731)
基金項(xiàng)目:
國家自然科學(xué)基金(61101033, 61076096)，國家863計(jì)劃項(xiàng)目(2011AA010201)，清華大學(xué)自主科研計(jì)劃(20141081231)和國家高科技中央高?；究蒲袠I(yè)務(wù)費(fèi)(ZYGX 2011J118)
Low-complexity Error Correction Algorithms for Redundant Residue Number Systems
-
1.
(Department of Mathematics, Tsinghua University, Beijing 100084, China)
-
2.
(National Key Laboratory of Science and Technology on Communications, University of Electronic Science and Technology of China, Chengdu 611731, China)
-
摘要: 余數(shù)系統(tǒng)由于具有增強(qiáng)傳輸信息在并行系統(tǒng)中魯棒性的優(yōu)勢，已被廣泛應(yīng)用在無線局域網(wǎng)(WLAN)以及碼分多址通信技術(shù)(CDMA)等領(lǐng)域。而余數(shù)系統(tǒng)中的糾錯(cuò)檢錯(cuò)是保證傳輸數(shù)據(jù)可靠性和高效性的關(guān)鍵問題。該文根據(jù)有限環(huán)上剩余類的性質(zhì)提出溢出判定定理，不重復(fù)判斷定理和唯一性區(qū)間搜索定理，并在此基礎(chǔ)上進(jìn)一步提出采用模運(yùn)算代替?zhèn)鹘y(tǒng)中國剩余定理進(jìn)行快速恢復(fù)的單錯(cuò)誤糾錯(cuò)算法，將復(fù)雜度降低為O(k,r)；提出不重復(fù)判定糾錯(cuò)算法；并對于一般錯(cuò)誤情形，設(shè)計(jì)通過比較算子實(shí)現(xiàn)的搜索糾錯(cuò)算法。其中搜索糾錯(cuò)算法能直接實(shí)現(xiàn)系統(tǒng)最大糾錯(cuò)能力，且避免依靠復(fù)雜模運(yùn)算算子實(shí)現(xiàn)，系統(tǒng)吞吐率得以提高；與傳統(tǒng)算法相比，計(jì)算復(fù)雜度由多項(xiàng)式級降低至對數(shù)級。
-
關(guān)鍵詞:
- 信息傳輸 /
- 編碼理論 /
- 中國剩余定理 /
- 冗余余數(shù)系統(tǒng) /
- 糾錯(cuò)檢錯(cuò)
Abstract: Redundant Residue Number System (RRNS) is widely used in communication systems for WLAN (Wireless LAN) and CDMA (Code Division Multiple Access) etc. due to its strong ability to enhance robustness of information in parallel processing environments. Error detection and correction of RRNS is an important guarantee for information reliability in communication systems. The overflow detection theorem, the unique theorem, and the searching theorem are proposed and proved in the paper based on properties of residue classes in finite rings. With the theorems, a single-error-correction algorithm using modular operations with reduced complexityO(k,r) is proposed. The uniqueness test algorithm is proposed. Furthermore, for any general types of errors, the searching multiple-error-correction algorithm is proposed. The computational complexity of the searching multiple-error- correction algorithm is reduced from polynomial order to logarithmic order according to the analysis, and the method can reach the extreme correction capability efficiently with only comparison operations instead of complex modular arithmetic. -
Madhukumar A S, Chin F, and Premkumar A B. Incremental redundancy and link adaptation in wireless local area networks using residue number systems[J]. Wireless Personal Communication, 2003, 55(27): 321-336. Pham Duc-Minh, Premkumar A B, and Madhukumar A S. Error detection and correction in communication channels using inverse gray RSNS Codes[J]. IEEE Transactions on Communications, 2011, 59(4): 975-986. Yang L L and Hanzo L. A residue number system based parallel communication scheme using orthogonal signaling- part I: system outline[J]. IEEE Transactions on Vehicular Technology, 2002, 51(6): 1534-1546. Yang L L and Hanzo L. A residue number system based parallel communication scheme using orthogonal signaling- part II: multipath fading channels[J]. IEEE Transactions on Vehicular Technology, 2002, 51(6): 1547-1559. Keller T, Liew T H, and Hanzo L. Adaptive redundant residue number system coded multicarrier modulation[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(11): 2292-2301. Yang Lie-liang and Hanzo L. Redundant residue number system based error correction codes[C]. IEEE 54th Vehicular Technology Conference, Atlantic, USA, 2001, 3: 1472-1476. Krishna H, Lin K Y, and Sun Jenn-dong. A coding theory approach to error control in redundant residue number systems. I. theory and single error correction[J]. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1992, 39(1): 8-17. Sun Jenn-dong and Krishna H. A coding theory approach to error control in redundant residue number systems. II. Multiple error detection and correction[J]. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1992, 39(1): 18-34. Goldreich O, Ron D, and Sudan M. Chinese remaindering with errors[J]. IEEE Transactions on Information Theory, 2000, 46(4): 1330-1338. Mandelbaum D M. On a class of arithmetic codes and a decoding algorithm (Corresp.)[J]. IEEE Transactions on Information Theory, 1976, 22 (1): 85-88. Goh V T and Siddiqi M U. Multiple error detection and correction based on redundant residue number systems[J]. IEEE Transactions on Communications, 2008, 56(3): 325-330. Lei Li and Hu-Jian-hao. Joint redundant residue number systems and module isolation for mitigating single event multiple bit upsets in datapath[J]. IEEE Transactions on Nuclear Science, 2010, 57(6): 3779-3786. Lei Li and Hu-Jian-hao. Redundant residue number systems based radiation gardening for datapath[J]. IEEE Transactions on Nuclear Science, 2010, 57(4): 2332-2343. Pontarelli S, Cardarilli G C, Re M, et al.. A novel error detection and correction technique for RNS based FIR filters[C]. IEEE International Symposium on Defect and Fault Tolerance of VLSI Systems (DFTVS), Boston, USA, 2008: 436-444. -
計(jì)量
- 文章訪問數(shù): 1450
- HTML全文瀏覽量: 133
- PDF下載量: 667
- 被引次數(shù): 0
下載:
