伽羅瓦域線性變換器格柵系統的製作方法
2023-06-10 10:16:36
專利名稱：伽羅瓦域線性變換器格柵系統的製作方法
技術領域：
本發明涉及一種改進的伽羅瓦域線性變換器格柵系統，並且更具體地涉及一種可以在單周期中對一個或多個位以及/或者甚至輸出位置換進行完整的格柵運算的系統。
相關申請本申請要求Stein等於2003年4月8日申請的標題為「Entitledmethod to predict trellis output using the FG-2 ALU(利用FG-2 ALU預測格柵輸出的方法)」的美國60/461,267號臨時申請的優先權。
背景技術：
前向糾錯(FEC)的用途是通過對經信道傳送的數據添加一些細心設計的冗餘信息改進該信道的能力。添加該冗餘信息的進程稱為信道編碼。卷積編碼和塊編碼是信道編碼的二種主要形式。卷積代碼在串行數據上運算，一次一個位或幾個位。塊代碼在相對大(典型地高達二百字節)的消息塊上運算。在一些情況下卷積代碼可能比塊代碼更方便，因為前者連續產生冗餘位和糾錯。
格柵是一種設備，用於通過擴展位以對位編碼從而例如為檢錯引入冗餘。格柵由包含線性反饋移位寄存器(LFSR)的觸發器以及包含模2加法器的「異或」門構成。由於LFSR，卷積代碼具有存儲器。例如，二個或三個或更多的輸入可產生三個或四個或更多的信道符號的輸出，這些符號不僅取決於當前的輸入位組塊還取決於以前的決。存在許多可能需要實現的不同格柵系統基本1:2編碼器，基本1:3編碼器或者任何基本n:m編碼器。格柵系統可能是可編程的或者可能涉及硬體解決辦法。常規可編程格柵的一個問題是，為了產生信道符號它們需要在每個位上進行數個周期的運算。典型辦法涉及實現要求大量相加或移位運算的線性反饋移位寄存器。另外，所產生的信道位可能不處於後繼處理所需的次序上。儘管硬體解決方案對於某特定功能更有效，但不能重新配置它們以適應許多可能需要的不同類型的格柵。
發明內容
從而本發明的一個目的是提供一種伽羅瓦域線性變換器格柵系統。
本發明的另一個目的是提供一種更快的並且可以把信道符號輸出置換成任何希望次序以適應後繼處理的伽羅瓦域線性變換器格柵系統。
本發明的再一個目的是提供一種可在單個周期內從一個或多個位預測多個輸出信道符號的伽羅瓦域線性變換器格柵系統。
本發明的再一個目的是提供一種可在一個周期內並行地從若干輸入位預測輸出的伽羅瓦域線性變換器格柵系統。
本發明的再一個目的是提供一種還可配置成完成各種獨立的輸入/輸出位置換的伽羅瓦域線性變換器格柵系統。
可以通過採用一個伽羅瓦域線性變換器矩陣、一個輸入選擇電路以及一個可編程存儲設備實現一種能並行地接收一個或多個位並能以直接或置換形式提供輸出信道符號的快得多、簡單得多的可重配置格柵系統，從而實現本發明，其中該輸入選擇電路用於對該矩陣提供一個或多個格柵位流中的多個輸入位以及該矩陣的格柵狀態輸出，而該可編程存儲設備用於設定該矩陣以對一個或多個格柵位流以及格柵狀態輸出進行多周期伽羅瓦域線性變換從而在單個周期內提供多個格柵輸出信道符號或者甚至置換後的格柵輸出通道符號以及新的格柵狀態。
本發明特徵在於一種伽羅瓦域線性變換器格柵系統，其包括一個伽羅瓦域線性變換器格柵矩陣以及一個用於對該矩陣提供一個或多個格柵位流中的多個輸入位以及該矩陣的格柵狀態輸出的輸入選擇電路。一個可編程存儲設備配置該矩陣以對該一個或多個格柵位流以及格柵狀態進行多周期伽羅瓦域線性變換從而在單個周期中提供多個格柵輸出信道符號以及新的格柵狀態輸出。
在一優選實施例中該矩陣可包括多個單元，每個單元包括一個「異或」邏輯電路，以及一個其輸出端連接到該「異或」邏輯電路上而輸入端連接到該輸入選擇電路以接收輸入位組的「與」邏輯電路。該可編程存儲設備可包括多個存儲單元，每個存儲單元編程成使能不同的伽羅瓦域線性變換。可能存在一個控制器電路，用來重配置該可編程存儲設備以把格柵輸出信道符號置換到預定次序中。該控制器電路還可以重配置該可編程存儲設備以便在該矩陣的每個行和列中只啟動一個單元從而把一給定的輸入位模式置換成一種不同的輸出位模式。
從下面的對優選實施例和附圖的說明業內人士會想到其它目的、特徵和優點，附圖中圖1是依據本發明的可重配置伽羅瓦域線性變換器格柵系統的簡化方塊圖；圖2A是典型現有技術ADSL Modem格柵系統的硬體線性反饋移位寄存器實現的示意方塊圖；圖2B是圖表I，說明八個時鐘周期上圖2的現有技術ADSL數據機格柵的四狀態情況；圖3A是圖1的可重配置伽羅瓦域線性變換器格柵系統更詳細示意方塊圖；圖3B和3C是圖表II和III，說明圖3A的伽羅瓦域線性變換器格柵系統中出現的二種四狀態情況；圖4是圖3的伽羅瓦域線性變換器矩陣的更詳細示意圖，其配置成在一個周期中從輸入位組產生格柵輸出信道符號；圖5是圖3的伽羅瓦域線性變換器矩陣的示意圖，其重配置成在一個周期中產生對輸入位組置換的格柵輸出信道符號；圖6是圖3的伽羅瓦域線性變換器格柵系統的更詳細示意圖；圖7是帶有可編程存儲設備的矩陣單元的示意圖；圖8是本發明的伽羅瓦域線性變換器格柵系統的示意方塊圖，具有帶有多個可編程部件平面和一個用來配置並再配置它的控制器電路；圖9A-9H示意說明利用本發明的可編程伽羅瓦域線性變換器格柵系統達到的置換的樣本。
具體實施例方式
除了下面說明的優選實施例或各實施例之外，本發明能為其它實施例並且能在各種方式實現或完成。從而應理解，在應用上本發明不受限於下面的說明描述的或在附圖中示出的結構細節和構件設置。
圖1中示出依據本發明的伽羅瓦域線性變換器格柵系統10，其接收概括地用u3、u2和u1標記的一個或多個格柵位流中的若干輸入位以及用Sn標記的該矩陣的格柵狀態輸出，該系統從這些輸入產生輸出12以及用Sn+1標記的下個或新的格柵狀態輸出14。
圖2A中示出在硬體中用線性反饋移位寄存器(LFSR)22實現的典型格柵系統，例如ADSL數據機格柵22。線性反饋移位寄存器22包括四個存儲設備即觸發器24、26、28和30，它們代表該線性反饋移位寄存器的狀態s0、s1、s2和s3。格柵位流u3、u2和u1作為位流u30、u31、u32...u37...、u20、u21、u22、u23...u27...u10、u11、u12、u13...u17...出現在各輸入端32上。位流u3在輸入32上直接提供輸出v0。輸出v1是響應u3輸入和u1輸入通過「異或」門34產生的。輸出w0是響應u3和u2輸入通過「異或」門36產生的。輸出w1是響應所有輸入u3、u2、u1並加上線40上的線性反饋移位寄存器22的輸出狀態S3通過「異或」門38提供的。儘管格柵系統20響應概括地用u3、u2、u1表示的各個特定格柵位u30、u31、u32...u37...、u20、u21、u22、u23...u27...u10、u11、u12、u13...u17...快速完成運算以得到輸出v0、v1、w0、w1，它具有它的硬體專門為ADSL數據機格柵功能服務從而不能方便地為其它任何用途重新配置的缺點。
在操作中每個時鐘周期下在圖2B的圖表II的列50中示出狀態s0、s1、s2和s3。
圖2A的格柵專用於完成特定格柵的功能並且在ADSL數據機格柵的情況下一次只可以處理一個位，而圖3A的本發明的伽羅瓦域線性變換器格柵系統10a根據具體應用允許的伽羅瓦域線性變換器矩陣的尺寸可以同時處理四個、八個、十二個、十六個或任何數量的位。這在圖3A中示出，其中廣義化格柵位流輸入u10-u13、u20-u23、u30-u33示出全部同時接收。對第一時刻或第一個時鐘周期用z10到z13-、y20到y23以及x30到x33示出特定的位。由於在該具體例子中GFLT格柵系統10一次接收四位，它的真伽羅瓦域變換器形式下的輸出將代表和第四個時鐘周期或圖表I中的三號時鐘周期對應的輸出，這在圖2B中用圖表I的框區52強調。從而在圖2B圖表1中的54、56、58和60示出的狀態s0、s1、s2和s3的值是圖3A中的新格柵狀態54a、56a、58a和60a。它們是新的格柵狀態s0n+1、s1n+1s2n+1、s3n+1並且反饋到格柵輸入端s3n、s2n、s1n、s0n。從而依據本發明的伽羅瓦域線性變換器格柵系統的第一時刻或第一時鐘周期產生和現有技術系統20的第四時鐘周期或3號時鐘周期相同的輸出。這樣在一個周期中不是處理一個位而是處理四個(或八個或十二個或任何其它數量)的位。相比之下在任何其它軟體可重配置系統為完成此會需要幾個周期。
在圖3B圖表II中用時鐘周期0標記的下個或第二時鐘周期，於列51中把狀態S0n+1示成是s3、y21(y21是u21的當前值)、s0、y20(y20是u20的當前值)以及z12(z12是u12的當前值)的「異或」組合。這可以展開如第二列53中所示並且接著如第三列55中所示消除冗餘(模2加)以提供下個格柵狀態，對s1n+1s2n+1s3n+1完成相同的工作。不以圖表形式列出輸出v0、v1、w0和w1，因為它們是信號的直接「異或」組合例如如圖4的伽羅瓦域線性變換格柵系統矩陣60上所示。可以看出，通過使能矩陣60的選定行和列相交處的「異或」門單元62得到圖表I和II中所需的輸出。例如，參照圖3B的圖表II，s3的值可以看成是s1、s2、s3、u21、u22、u13和u10的「異或」組合，而例如對於w03其表達式應是u33和u23的簡單「異或」運算，對於v12它會是u32和u12的「異或」，等等。這樣在單個周期的運算中可以處理四個位以便提供輸出和狀態，而在諸如圖2A的ADSL數據機格柵所示的硬體實現下這通常需要四個周期，另外在可重配置的軟體實現下則需要多得多的運算周期。
本發明的另一個優點是於該矩陣在按任何希望的次序操縱輸出的靈活性從而可以在希望的形式下裝配格柵輸出信道符號。例如，代替如圖4中所示在單個周期後給出輸出(其中組合從0到3的所有w1，從0到3的所有w0，並且組合所有v1和所有v0)，可以替代地如圖5中所示組合w1[3]、wo[3]、v1[3]、v0[3]，組合w1[2]、w0[2]、v1[2]、v0[2]，等等。
圖6的伽羅瓦域線性變換器格柵系統可包括矩陣70和輸入選擇電路72，該電路72可包括輸入或「u」寄存器74、狀態或「s」寄存器76、若干多路復用器78、80、82、84以及對應數量的鎖存器86、88、90、92。最初，由於所有的狀態「s」為零，寄存器76的級94上的所有輸入都為零。在輸入寄存器74的第一級96上不存在格柵位流位組，但是存在先前識別的格柵位流位組級98上的位u10、u11、u12、u13；級100上的位u20、u21、u22、u23；以及級102上的位u30、u31、u32、u33。當它們和寄存器76的級94中的零狀態一起存在時，伽羅瓦域線性變換器矩陣60b立即在一個周期中預測輸出並且在輸出寄存器104中產生它。現在狀態條件s00、s01、s02、s03也駐留在輸出寄存器104中並反饋到狀態寄存器76的級94，接著下一組四個位中的每一組和該狀態一起處理以在輸出寄存器104中提供下個輸出，從而執行參照圖3A、3B、4和5解釋的運算。圖7中的每個單元62a可以包括一個輸出端112和下個單元連接並且輸入端114和前一個單元的輸出連接的「異或」門110，但是行中第一單元的輸入端和零連接而各行中的最後一個單元代表該矩陣的輸出。「與」門116對「異或」門110提供另一個輸入，並且可編程存儲設備即觸發器118響應線120上的寫信號和控制「與」門116的禁止從而啟動單元62a。如圖6中所示每個可編程存儲單元或觸發器118可以在一個分立平面122上獨立於其餘單元實現。接著該控制電路簡單地定址觸發器的可編程平面122以便配置或重新配置該矩陣從而為任何具體的格柵實現服務。
這在圖8中圖解示出，其中控制器電路130，例如DSP、微處理器或序列發生器，控制一個或多個存儲平面122、122a、122b、122n。在美國專利3,658,864中示出伽羅瓦域線性變換器和輔助電路的結構，本文整體收錄它作為參考。可編程存儲設備122、122a、122b...122n的編程不限於只為不同的格柵操作重配置該矩陣，而是還可以在格柵運算之間重配置它，例如完成格柵輸入位流和格柵輸出信道符號之間的各種置換。存在二種通過重配置矩陣60的啟動單元62實現的置換類型。第一類型涉及輸入和輸出位組數量相等的置換。在此情況下對矩陣的每個行和列只啟動一個單元。第二類型涉及輸出位多於輸入位的置換(擴展)。在此情況下在矩陣的每行中只啟動一個單元。在圖9A-9H中示出這二種類型的典型置換，其中圖9A代表位前後交換(BitFlip)置換，圖9B代表位交織(Bit Interleave)置換，圖9C代表字節對換(Byte Swap)置換，圖9D代表位去交織(Bit Deinterleave)，圖9E代表字節拆包(Byte Unpack)，圖9F代表位擴展(Bit Expand)，圖9G代表字節打包(Byte Pack)，而圖9H代表右移位和合併字節(Shift Right and Merge Byte)。
下述例案整體收錄作為參考Stein等2002年1月18日申請的標題為「GALOIS FIELD LINEAR TRANSFORMER(伽羅瓦域線性變換器)」的美國專利申請10/051,533號(AD-239J)；Stein等2002年6月12日申請的標題為「PROGRAMMABLE DATA ENCRYPTIONENGINE(可編程數據加密機)」的美國專利申請10/170,267號(AD297J)；Stein等2002年5月1日申請的標題為「PROCONFIGURABLE INPUT GALOIS FIELD LINEARTRANSFORMER SYSTEM(可重配置輸入伽羅瓦域線性變換器系統)」的美國專利申請10/136,170號(AD-300J)。
儘管在一些圖中而並未在另一些圖中示出本發明的特定特徵，這只是出於方便，因為每種特徵可以和依據本發明的其它特徵中的任一個或全部進行組合。本文使用的詞「包含」、「包括」、「具有」和「帶有」是廣泛和綜合地解釋並且不限制任何物理互連。另外，本申請中公開的任何實施例並不應當成是唯一可能的實施例。
業內人士會從下面的權利要求書可以設想到其它實施例。
權利要求
1.一種伽羅瓦域線性變換器(GFLT)格柵系統，包括一個GFLT矩陣；一個輸入選擇電路，用於對所述矩陣提供在一個或多個格柵位流中的多個輸入位以及所述矩陣的一個格柵狀態輸出；以及一個可編程存儲設備，用於把所述矩陣配置成對所述一個或多個格柵位流以及格柵狀態輸出執行多周期伽羅瓦域線性變換，以在單個周期中提供多個格柵輸出信道符號和新的格柵狀態輸出。
2.如權利要求1的伽羅瓦域線性變換器格柵系統，其中所述矩陣包括多個單元，每個單元包括一個「異或」邏輯電路，以及一個「與」電路，其輸出端和該「異或」邏輯電路連接而輸入端和用於接收輸入位組的所述輸入選擇電路連接。
3.如權利要求1的伽羅瓦域線性變換器格柵系統，其中所述可編程存儲設備包括多個存儲單元，每個存儲單元被編程以啟動一個不同的伽羅瓦域線性變換。
4.如權利要求1的伽羅瓦域線性變換器格柵系統包括一個控制器電路，用於重配置所述可編程存儲設備以將所述格柵輸出信道符號置換成預定次序。
5.如權利要求1的伽羅瓦域線性變換器格柵系統，包括一個控制器電路，用於重配置所述可編程存儲設備以只啟動所述矩陣的每個行和列中的一個單元從而將給定輸入位模式置換成一個不同的輸出位模式。
6.如權利要求1的伽羅瓦域線性變換器格柵系統，其中所述輸入選擇電路包括一個輸入寄存器、一個狀態寄存器和一個切換系統電路，用於選擇性地將來自所述輸入寄存器和狀態寄存器之一或二者的數據輸入到所述矩陣。
7.如權利要求1的伽羅瓦域線性變換器格柵系統包括一個控制器電路，用於重配置所述可編程存儲設備以只啟動所述矩陣的每行中的一個單元，從而將給定的輸入位模式擴展成一個不同的輸出位模式。
8.一種伽羅瓦域線性變換器(GFLT)格柵系統，包括一個GFLT矩陣；一個輸入選擇電路，用於向所述矩陣提供一個或多個格柵位流中的多個輸入位以及所述矩陣的一個格柵狀態輸出；以及一個可編程存儲設備，用於將所述矩陣配置成對所述一個或多個格柵位流和格柵狀態輸出執行多周期伽羅瓦域線性變換，以在單個周期中提供多個置換後的格柵輸出信道符號以及新的格柵狀態輸出。
全文摘要
一種伽羅瓦域線性變換器格柵系統包括一個伽羅瓦域線性變換器矩陣；一個輸入選擇電路，用於對該矩陣提供一個或多個格柵位流中的多個輸入位以及該矩陣的格柵狀態輸出；以及一個可編程存儲設備，用於把該矩陣配置成對該一個或多個格柵位流以及格柵狀態輸出進行多周期伽羅瓦域線性變換從而在單個周期中提供多個格柵輸出信道符號以及新的格柵狀態輸出。
文檔編號G06F15/00GK1926531SQ200480014207
公開日2007年3月7日 申請日期2004年4月7日 優先權日2003年4月8日
發明者優素伏·施泰因, 哈伊姆·樸瑞姆 申請人:阿納洛格裝置公司