基于RRNS雙錯(cuò)誤糾錯(cuò)算法研究.pdf

1、隨著信息技術(shù)迅猛發(fā)展的今天，人們對(duì)超大規(guī)模集成電路Very Large Scale I ntegration(VLSI)技術(shù)的要求日趨增高。目前集成電路工藝尺寸已經(jīng)快接近極限了，摩爾定律也即將面臨失效。于是，人們對(duì)提高電路或系統(tǒng)性能的方式不再僅僅只靠縮小工藝尺寸來(lái)實(shí)現(xiàn)了，而是希望通過(guò)對(duì)算法前端進(jìn)行改進(jìn)優(yōu)化等方式來(lái)解決系統(tǒng)速度，面積以及低功耗等難題。
　　在日益復(fù)雜的各種系統(tǒng)中，如通信系統(tǒng)、圖像處理系統(tǒng)、密碼系統(tǒng)、雷達(dá)系統(tǒng)、數(shù)據(jù)處理

2、系統(tǒng)等等均面臨著VLSI性能的問(wèn)題，于是并行處理技術(shù)成為各個(gè)領(lǐng)域研究的對(duì)象。而余數(shù)系統(tǒng)(RNS)就是一個(gè)典型的并行數(shù)值表征系統(tǒng)，具有許多優(yōu)良特性，如并行性、無(wú)權(quán)性、容錯(cuò)性等等，故成為重點(diǎn)研究對(duì)象之一。在距今20多年里，余數(shù)系統(tǒng)在數(shù)字信號(hào)處理以及通信領(lǐng)域的研究越來(lái)越多，國(guó)內(nèi)外的研究成果也頗多。而目前對(duì)于余數(shù)系統(tǒng)的研究越來(lái)越多集中在容錯(cuò)性方向，通過(guò)編碼譯碼算法使信號(hào)在余數(shù)系統(tǒng)中并行傳輸?shù)竭_(dá)后能夠?qū)λM(jìn)行檢錯(cuò)糾錯(cuò)恢復(fù)正確余數(shù)向量，從而有效增強(qiáng)

3、系統(tǒng)的可靠性。
　　基于以上情況，本文圍繞余數(shù)系統(tǒng)糾錯(cuò)方向進(jìn)行了深入研究，目前已有的糾錯(cuò)算法均存在以下幾個(gè)問(wèn)題：1.大部分糾錯(cuò)算法都停留在單個(gè)余數(shù)錯(cuò)誤糾錯(cuò)上，并沒(méi)有進(jìn)行2個(gè)或2個(gè)以上糾錯(cuò)的深入研究；2.現(xiàn)有的雙錯(cuò)誤或多個(gè)糾錯(cuò)算法復(fù)雜度太高以及VLSI性能較差，比如延時(shí)、面積太大等；本文從以上兩個(gè)問(wèn)題出發(fā)，研究了基于RRNS雙錯(cuò)誤糾錯(cuò)算法，明顯降低了算法復(fù)雜度，提升了VLSI性能。
　　本文針對(duì)以上問(wèn)題，提出基于冗余余數(shù)系統(tǒng)(

4、RRNS)的雙錯(cuò)誤糾錯(cuò)算法研究，主要內(nèi)容如下：
　　1.擴(kuò)展了一種雙錯(cuò)誤糾錯(cuò)算法理論以及提出了改進(jìn)糾錯(cuò)算法理論(非冗余部分)，雙錯(cuò)誤糾錯(cuò)算法理論是基于修正糾正子進(jìn)行糾錯(cuò)，首先建立糾正子與錯(cuò)誤之間的映射關(guān)系，然后為減小延時(shí)通過(guò)降低模值來(lái)引入近似糾正子概念并將其送入多通道修正為修正糾正子，接著采用多個(gè)映射表來(lái)映射錯(cuò)誤輸出；改進(jìn)糾錯(cuò)算法理論是基于近似糾正子進(jìn)行糾錯(cuò)，通過(guò)遍歷量值所有可能值直接建立近似糾正子與錯(cuò)誤的映射關(guān)系，從而達(dá)到只需一

5、個(gè)映射表完成檢錯(cuò)及后續(xù)糾錯(cuò)過(guò)程。本文對(duì)冗余部分糾錯(cuò)提出了兩種算法：冗余修正匹配算法和冗余遍歷映射算法，并給出了理論說(shuō)明。
　　2.根據(jù)修正糾正子糾錯(cuò)算法理論及近似糾正子糾錯(cuò)算法理論建立了兩種基于RRNS譯碼糾錯(cuò)算法體系架構(gòu)。這兩種架構(gòu)主要包含三大模塊：近似基擴(kuò)展與近似糾正子計(jì)算模塊、檢錯(cuò)模塊以及糾錯(cuò)模塊。在這兩種架構(gòu)中，所有余數(shù)送入獨(dú)立并行運(yùn)算通道，互不干擾，完成近似糾正子計(jì)算。這兩種架構(gòu)區(qū)別僅在于檢錯(cuò)模塊，第一種架構(gòu)基于修正糾正

6、子進(jìn)行檢錯(cuò)，第二種架構(gòu)基于近似糾正子進(jìn)行檢錯(cuò)。糾錯(cuò)模塊均為通過(guò)OR與MUX門來(lái)逐級(jí)糾錯(cuò)選擇，這種基于差錯(cuò)映射的架構(gòu)既提升了系統(tǒng)速度又節(jié)省了硬件資源?？紤]到兼容性問(wèn)題，本文也對(duì)該算法架構(gòu)糾單個(gè)錯(cuò)誤進(jìn)行了分析討論。
　　3.對(duì)本文算法完成Verilog HDL代碼編寫(xiě)并搭建VCS測(cè)試平臺(tái)進(jìn)行驗(yàn)證，為實(shí)現(xiàn)完整驗(yàn)證并進(jìn)一步搭建基于 FPGA的測(cè)試平臺(tái)對(duì)本文算法進(jìn)行驗(yàn)證。最后采用Design Compiler工具并使用SMIC90工藝庫(kù)完成

7、代碼設(shè)計(jì)綜合并進(jìn)行門級(jí)仿真以及形式驗(yàn)證。本文也做了兼容1個(gè)錯(cuò)誤的驗(yàn)證，通過(guò)生成單錯(cuò)誤映射表再搭建對(duì)應(yīng)的測(cè)試平臺(tái)進(jìn)行驗(yàn)證，保證本文算法可以兼容單個(gè)錯(cuò)誤糾錯(cuò)。本文映射表地址生成均通過(guò)matlab編程得出再導(dǎo)入Verilog中。
　　4.本文對(duì)國(guó)外典型的兩種基于 RRNS的雙錯(cuò)誤或多個(gè)錯(cuò)誤糾錯(cuò)算法進(jìn)行了介紹：基于一致性方程檢測(cè)的雙錯(cuò)誤糾錯(cuò)算法與基于中國(guó)剩余定理(CRT)的迭代改進(jìn)糾錯(cuò)算法。對(duì)這兩種算法進(jìn)行了代碼設(shè)計(jì)、驗(yàn)證及綜合，用于對(duì)比

8、本文算法的性能。本文對(duì)有效動(dòng)態(tài)范圍位寬W=∑ki=1[log2mi]=30bit的各算法將從延時(shí)，面積等性能方面進(jìn)行對(duì)比評(píng)估，其中本文修正算法較對(duì)比兩種算法延時(shí)分別減少70.9％和74.3%，而面積則分別增加了44.9%和184%，本文近似算法較對(duì)比兩種算法延時(shí)分別減少74.7%和77.7%，面積則一個(gè)減少了30.9%而較另一個(gè)增加了35.3%；從“delay×area”性能角度綜合對(duì)比，本文修正算法較對(duì)比算法分別較少了57.8%和27

9、.1%，本文近似算法較對(duì)比算法分別減少了82.5%和69.9%，故本文算法更適合 VLSI實(shí)現(xiàn)。為評(píng)估各算法在不同有效動(dòng)態(tài)范圍的性能趨勢(shì)，還做了8bit、16bit的對(duì)比分析，其中為8bit時(shí)，本文修正算法較文獻(xiàn)兩種算法綜合對(duì)比分別減少了61.5%和93.5%，本文近似算法則分別減少了84.1%和97.3%；為16bit時(shí)，本文修正算法較文獻(xiàn)兩種算法綜合對(duì)比分別減少了65.0%和62.0%，本文近似算法則分別減少了82.2%和80.6%