運算電路、編碼電路以及解碼電路的製作方法

2023-04-30 18:40:47

本發明涉及運算電路、編碼電路以及解碼電路。

背景技術：

XOR(異或)運算例如在生成附加於發送數據的奇偶校驗位時等進行。

近年來，為了避免因在使用了TCP(Transmission Control Protocol：傳輸控制協議)/IP(Internet Protocol：網際網路互聯協議)的通信時所產生的數據包丟失所造成的通信速度的降低，提出了RPS(Random Packet Stream：自動恢復接受放丟失的數據包的功能)技術。RPS技術是自動生成數據轉送時消失的數據包的技術。在RPS技術中，為了生成使用於數據包恢復的編碼數據(冗餘數據)，利用發送裝置多次進行固定的數據量的數據塊間的XOR運算。

專利文獻1:日本特開平11－237997號公報

專利文獻2:日本特開2001－147827號公報

專利文獻3:特開平11－102301號公報

然而，如基於RPS技術的編碼處理那樣，利用多個數據塊的組合多次反覆XOR運算的處理若利用軟體進行則花費處理時間，被認為不能夠應對通信速度的高速化發展的狀況。

鑑於此，可以考慮利用硬體進行XOR運算。然而，僅使軟體硬體化，有可能不會帶來運算的高速化。例如若反覆將某個數據塊間的XOR運算結果暫時儲存於存儲器，並在該結果與其它的數據塊間進行XOR運算這樣的處理，則在存儲器的數據轉送速度慢的情況下，導致處理時間變長。

技術實現要素：

根據發明的一觀點，提供一種運算電路，該運算電路具有：多個存儲器，保持成為進行異或運算的單位的數據塊；多個選擇電路，接受選擇信號，並基於上述選擇信號來選擇從上述多個存儲器讀出的多個上述數據塊中的使用於異或運算的2個以上的數據塊；以及1個或者多個異或運算電路，進行基於由上述多個選擇電路選擇出的上述2個以上的數據塊的異或運算。

另外，根據發明的一觀點，提供一種編碼電路，該編碼電路具有：多個存儲器，保持成為進行異或運算的單位的數據塊；多個選擇電路，接受選擇信號，並基於上述選擇信號來選擇從上述多個存儲器讀出的多個上述數據塊中的使用於異或運算的2個以上的數據塊；以及1個或者多個異或運算電路，進行基於由上述多個選擇電路選擇出的上述2個以上的數據塊的異或運算，生成編碼數據。

另外，根據發明的一觀點，提供一種解碼電路，該解碼電路具有：多個存儲器，保持成為進行異或運算的單位的編碼數據即數據塊；多個選擇電路，接受選擇信號，並基於上述選擇信號來選擇從上述多個存儲器讀出的多個上述數據塊中的使用於異或運算的2個以上的數據塊；1個或者多個異或運算電路，進行基於由上述多個選擇電路選擇出的上述2個以上的數據塊的異或運算，生成解碼數據。

根據公開的運算電路、編碼電路以及解碼電路，能夠使運算處理高速化。

本發明的上述以及其它的目的、特徵以及優點根據與表示作為本發明的例子而優選的實施方式的添加的附圖相關的以下的說明變得更清楚。

附圖說明

圖1是表示根據第一實施方式的運算電路的一個例子的圖。

圖2是對RPS編碼處理的一個例子進行說明的圖。

圖3是表示信息處理裝置的一個例子的圖。

圖4是對進行RPS編碼處理的FPGA的一個例子進行說明的圖。

圖5是表示根據第二實施方式的編碼電路的一個例子的圖。

圖6是表示控制電路的一個例子的圖。

圖7是表示RPS編碼矩陣的一個例子的圖。

圖8是表示RPS編碼處理的一個例子的流程的流程圖。

圖9是說明針對通過RPS編碼處理所得到的編碼數據的解碼處理的一個例子的圖。

圖10是表示根據第二實施方式的解碼電路的一個例子的圖。

圖11是對接收編碼矩陣的生成例進行說明的圖。

圖12是表示生成的接收編碼矩陣的一個例子的圖。

圖13是表示解碼向量的生成處理的一個例子的流程的流程圖。

圖14是表示更新後的接收編碼矩陣的一個例子的圖。

圖15是表示矩陣ops的一個例子的圖。

圖16是表示矩陣ops的列向量(解碼向量)與通過該列向量所解碼的數據塊的關係的一個例子的圖。

圖17是表示根據第二實施方式的編碼電路的變形例的圖(其1)。

圖18是表示根據第二實施方式的編碼電路的變形例的圖(其2)。

圖19是表示根據第二實施方式的編碼電路的變形例的圖(其3)。

圖20是對編碼處理的一個例子的流程進行說明的圖。

具體實施方式

以下，參照附圖，對用於實施發明的方式進行說明。

(第一實施方式)

圖1是表示根據第一實施方式的運算電路的一個例子的圖。

運算電路1例如是進行編碼處理的編碼電路或者進行解碼處理的解碼電路等。

運算電路1具有存儲器M0～M15、選擇電路2a～2p、XOR電路3a～3o、被輸入選擇信號的輸入端子P1、輸出XOR運算結果的輸出端子P2。此外，將電路元件間連接起來的信號線例如可以捆綁64位寬度等多個位。

存儲器M0～M15例如是RAM(Random Access Memory：隨機存取存儲器)，對成為進行XOR運算的單位的多個數據塊進行保持。數據塊例如是按照一定的數據尺寸分割編碼對象數據而得的塊。在圖1的例子中，16個數據塊分別被保持在存儲器M01～M15的任意一個中。另外，存儲器M0～M15分別將保持的數據塊輸出給選擇電路2a～2p。

選擇電路2a～2p接受從輸入端子P1輸入的選擇信號，並基於該選擇信號來選擇是否將保持在存儲器M0～M15中的數據塊使用於XOR運算。作為選擇電路2a～2p，能夠使用AND電路(邏輯和運算電路)。選擇電路2a～2p並不限於AND電路，但通過使用AND電路，能夠成為簡單的電路。

以下，對選擇電路2a～2p為AND電路的情況進行說明。

選擇電路2a～2p進行存儲器M0～M15輸出的數據塊和16位的選擇信號的AND運算，並將其運算結果輸出給XOR電路3a～3h。此時，根據從輸入端子P1輸入的16位的選擇信號的成為「1」的位，從選擇電路2a～2p輸出保持在存儲器M0～M15中的多個數據塊的一個或者多個。

在圖1的上側，假定運算電路1進行基於RPS技術的編碼處理(以下稱為RPS編碼處理)的情況，示出RPS編碼矩陣的一個例子。RPS編碼矩陣被存儲在未圖示的存儲部中，作為選擇信號，16位的列向量按順序被輸入至輸入端子P1。圖1的RPS編碼矩陣是16行30列的矩陣。列向量中的行與存儲器M0～M15對應。換句話說，在列向量中的某行的值為「1」時，保持在與該行對應的存儲器中的數據塊被使用於XOR運算。

例如列編號為17的列向量從輸入端子P1被輸入的情況下，存儲在與第1、第3、第5～第13、第15行對應的存儲器M0、M2、M4、…、M12、M14中的數據塊從選擇電路2a、2c、2e、…、2m、2o輸出。

另外，在列編號為25的列向量從輸入端子P1被輸入的情況下，保持在與第2、第4、…、第12、第14、第16行對應的存儲器M1、M3、…、M11、M13、M15中的數據塊從選擇電路2b、2d、…、2l、2n、2p輸出。

XOR電路3a～3o進行基於由選擇電路2a～2p選擇出的數據塊的XOR運算。XOR運算結果從輸出端子P2輸出。

XOR電路3a的2個輸入端子與選擇電路2a、2b的輸出端子連接，XOR電路3b的2個輸入端子與選擇電路2c、2d的輸出端子連接。另外，XOR電路3c的2個輸入端子與選擇電路2e、2f的輸出端子連接，XOR電路3d的2個輸入端子與選擇電路2g、2h的輸出端子連接。另外，XOR電路3e的2個輸入端子與選擇電路2i、2j的輸出端子連接，XOR電路3f的2個輸入端子與選擇電路2k、2l的輸出端子連接。另外，XOR電路3g的2個輸入端子與選擇電路2m、2n的輸出端子連接，XOR電路3h的2個輸入端子與選擇電路2o、2p的輸出端子連接。

XOR電路3i的2個輸入端子與XOR電路3a、3b的輸出端子連接，XOR電路3j的2個輸入端子與XOR電路3c、3d的輸出端子連接。另外，XOR電路3k的2個輸入端子與XOR電路3e、3f的輸出端子連接，XOR電路3l的2個輸入端子與XOR電路3g、3h的輸出端子連接。XOR電路3m的2個輸入端子與XOR電路3i、3j的輸出端子連接，XOR電路3n的2個輸入端子與XOR電路3k、3l的輸出端子連接。XOR電路3o的2個輸入端子與XOR電路3m、3n的輸出端子連接，XOR電路3o的輸出端子與輸出端子P2連接。

在圖1的例子中，如上述那樣XOR電路3a～3o連接成樹狀(二叉樹狀)。此外，XOR電路並不限於2個輸入，也可以為3個輸入以上，例如可以利用一個XOR電路進行從選擇電路2a～2p輸出的數據塊的XOR運算。

(運算電路1的動作例)

以下，對運算電路1的動作的一個例子進行說明。此外，在以下作為圖1所示那樣的RPS編碼矩陣的列向量是輸入給選擇電路2a～2p的選擇信號的情況進行說明。

對輸入端子P1按順序輸入列編號為0～29的列向量作為選擇信號。

在列編號為0～15的各列向量中，某一行的值為1，其它的行的值為0。在作為選擇信號而將這樣的列向量輸入到輸入端子P1時，保持在與值為1的行對應的存儲器中的數據塊從選擇電路2a～2p的任意一個輸出。從其它的選擇電路輸出0。

由此，從具有上述那樣的連接關係的XOR電路3a～3o的最後級的XOR電路3o輸出保持在存儲器M0～M15的任意一個中的數據塊本身。

在列編號為16～29的各列向量中，多個行的值為1。在作為選擇信號而將這樣的列向量輸入到輸入端子P1時，保持在與值為1的行對應的存儲器中的多個數據塊從選擇電路2a～2p的任意2個以上輸出。從其它的選擇電路輸出0。

由此，從具有如上述那樣的連接關係的XOR電路3a～3o的最後級的XOR電路3o輸出從選擇電路2a～2p的任意2個以上輸出的多個數據塊的XOR運算結果。

如以上那樣，根據本實施方式的運算電路1暫時利用多個存儲器M0～M15保持各數據塊，從自存儲器M0～M15讀出的多個數據塊通過選擇電路2a～2p選擇使用於運算的數據塊，並轉交給XOR電路3a～3o。通過這樣的並列化處理，如RPS編碼處理那樣在利用多個數據塊間的組合進行很多的XOR運算時，提高運算處理的效率，實現高速的運算。

(第二實施方式)

以下，作為進行XOR運算的運算電路的例子，對包含於發送電路，進行RPS編碼處理的編碼電路、以及包含於接收電路，對通過RPS編碼處理所編碼的編碼數據進行解碼的解碼電路進行說明。

首先，對RPS編碼處理的一個例子進行說明。

圖2是說明RPS編碼處理的一個例子的圖。

首先，在基於RPS編碼的處理中，數據被分割為固定尺寸的數據塊。此處，為了說明，16KB的數據被分割為每個1KB的16個數據塊，將分割成的端子塊設為塊b0～b15。

接下來，編碼電路從通過數據的分割而得到的塊b0～b15選擇一個或者多個，並通過選擇出的塊進行XOR運算，從而生成編碼數據d0～d15以及冗餘編碼數據e0～e13。

之後，對編碼數據等，作為數據包而在數據包報頭追加組合信息(在後述的例子中，圖7的RPS編碼矩陣的列向量)，再賦予通信數據包報頭後，通過UDP(User Datagram Protocol：用戶數據報協議)通信進行發送。此時，即使在傳送路徑上產生數據包的消失、替換，接收側通過對接收到的編碼數據等和接收到的組合信息(在後述的例子中，圖12的接收編碼矩陣)應用高斯消元法等，能夠對原始的發送數據進行解碼。

接下來，對使用於數據通信的信息處理裝置的一個例子進行說明。

圖3是表示信息處理裝置的一個例子的圖。

信息處理裝置4具有計算機5、和安裝在計算機5的功能擴展板6。計算機5具有CPU(Central Processing Unit：中央處理器)5A、主存儲部5B、PCIe(PCI express：總線接口)總線5C。在功能擴展板6上搭載存儲器晶片6A、FPGA(Field-Programmable Gate Array：現場可編程門陣列)6B、LAN(Local Area Network：區域網)連接器6C。另外，CPU5A和FPGA6B經由PCIe總線5C連接。

CPU5A從未圖示的HDD(Hard Disk Drive：硬碟驅動器)等讀出發送數據，並使主存儲部5B儲存。另外，對FPGA6B指示RPS編碼處理的執行等。

主存儲部5B儲存有發送數據、CPU5A的處理所需的各種數據。主存儲部5B例如使用RAM。

存儲器晶片6A通過FPGA6B具有的DMA(Direct Memory Access：直接內存存取)控制器儲存從主存儲部5B轉送來的數據。存儲器晶片6A例如使用RAM。

FPGA6B進行數據的RPS編碼處理等，生成通信用的數據包，並輸出給LAN連接器6C。

LAN連接器6C經由網絡將FPGA6B輸出的數據包轉送給未圖示的接收裝置等。

(FPGA6B的一個例子)

圖4是對進行RPS編碼處理的FPGA的一個例子進行說明的圖。

此外，在圖4中，執行發送數據的RPS編碼處理以外的控制以及功能的部分省略圖示。

FPGA6B具有PCIe接口6B1、存儲控制器6B2、通信處理電路6B3、控制電路7、編碼電路8。

PCIe接口6B1是I/O設備等構成的PCIe端點，針對經由PCIe總線5C轉送來的數據等進行物理層、數據鏈路層中的處理等。

存儲控制器6B2是將儲存在存儲器晶片6A中的數據分割為固定尺寸的數據塊，並轉送給BRAM(Block RAM：塊隨機存儲器)m0～m15的存儲器接口。存儲控制器6B2例如圖2所示，將16KB的數據分割為固定尺寸1KB的16個塊b0～b15，並轉送給BRAMm0～m15。

通信處理電路6B3針對編碼電路8輸出的編碼數據等進行網絡層、數據鏈路層、物理層中的處理等，生成通信用的數據包並輸出給LAN連接器6C。

控制電路7是進行編碼電路8生成編碼數據時的控制等的電路。控制電路7的電路構成後述。

編碼電路8是通過進行多個數據塊間的XOR運算來生成編碼數據的電路。在圖2的例子中，編碼電路8進行塊b0～b15間的XOR運算，並生成編碼數據d0～d15以及冗餘編碼數據e0～e13。

(編碼電路8的一個例子)

圖5是表示根據第二實施方式的編碼電路的一個例子的圖。

編碼電路8具有BRAMm0～m15、寄存器9a～9p、AND電路10a～10p、XOR電路11a～11o、寄存器12a～12o、輸入端子P3、P4、P5、輸出端子P6。

從控制電路7對輸入端子P3輸入使得能夠向BRAMm0～m15寫入數據塊的WE(Write Enable：允許寫入)信號。

從控制電路7對輸入端子P4輸入BRAMm0～m15寫入數據塊時的寫入地址信號、BRAMm0～m15讀出數據塊來輸出給AND電路10a～10p時的讀出地址信號。

從控制電路7對輸入端子P5為AND電路10a～10p輸入後述的RPS編碼矩陣的列向量的各要素。

從存儲器晶片6A經由存儲控制器6B2對編碼電路8供給被分割成固定尺寸的16個數據塊。

BRAMm0～m15若經由輸入端子P3、P4從控制電路7輸入寫入地址信號以及WE信號，則將供給的16個數據塊例如圖2的塊b0～b15分別1塊1塊地進行寫入儲存。另外，BRAMm0～m15若經由輸入端子P3從控制電路7輸入讀出地址信號，則分別讀出儲存的數據塊例如各64位，並輸出給寄存器9a～9p。

寄存器9a～9p連接在BRAMm0～m15的各個與AND電路10a～10b的各個之間。寄存器9a～9p對BRAMm0～m15輸出的數據塊進行保持，並調整保持的數據塊的AND電路輸出時機。例如寄存器9a～9b按照與未圖示的時鐘信號同步的時機，對從BRAMm0～m15供給的數據塊進行保持並輸出。在從BRAMm0～m15到AND電路10a～10p的距離有偏差的情況下，通過在AND電路10a～10p的輸入側設置這樣的寄存器9a～9p，能夠使向AND電路10a～10p的輸入時機一致。

AND電路10a～10p作為選擇電路發揮作用。AND電路10a～10p分別進行BRAMm0～m15輸出的數據塊和從輸入端子P5輸入的RPS編碼矩陣的各值(相當於選擇信號)的AND運算，並將其運算結果輸出給XOR電路11a～11h。此時，AND電路10a～10p分別選擇保持在與經由輸入端子P5輸入的列向量的值成為「1」的行對應的BRAMm0～m15中的數據塊並輸出。RPS編碼矩陣的列向量後述。

XOR電路11a～11o進行AND電路10a～10p選擇並輸出的數據塊間的XOR運算，且將其運算結果輸出給輸出端子P6。

XOR電路11a的2個輸入端子與AND電路10a、10b的輸出端子連接，XOR電路11b的2個輸入端子與AND電路10c、10d的輸出端子連接。另外，XOR電路11c的2個輸入端子與AND電路10e、10f的輸出端子連接，XOR電路11d的2個輸入端子與AND電路10g、10h的輸出端子連接。另外，XOR電路11e的2個輸入端子與AND電路10i、10j的輸出端子連接，XOR電路11f的2個輸入端子與AND電路10k、10l的輸出端子連接。另外，XOR電路11g的2個輸入端子與AND電路10m、10n的輸出端子連接，XOR電路11h的2個輸入端子與AND電路10o、10p的輸出端子連接。

XOR電路11i的2個輸入端子經由寄存器12a、12b與XOR電路11a、11b的輸出端子連接。XOR電路11j的2個輸入端子經由寄存器12c、12d與XOR電路11c、11d的輸出端子連接。另外，XOR電路11k的2個輸入端子經由寄存器12e、12f與XOR電路11e、11f的輸出端子連接。另外，XOR電路11l的2個輸入端子經由寄存器12g、12h與XOR電路11g、11h的輸出端子連接。XOR電路11m的2個輸入端子經由寄存器12i、12j與XOR電路11i、11j的輸出端子連接。XOR電路11n的2個輸入端子經由寄存器12k、12l與XOR電路11k、11l的輸出端子連接。XOR電路11o的2個輸入端子經由寄存器12m、12n與XOR電路11m、11n的輸出端子連接，XOR電路11o的輸出端子經由寄存器12o與輸出端子P6連接。輸出端子P6將XOR電路11a～11o進行的數據塊間的XOR運算結果作為編碼數據(包括前述的編碼數據和冗餘編碼數據)輸出給通信處理電路6B3(圖4)。

寄存器12a～12p具有與寄存器9a～9p同樣的功能，進行XOR電路11a～11o間的數據輸入輸出的時機調整。

在圖5的例子中，如上述那樣，XOR電路11a～11o遍及多級而連接成樹狀(二叉樹狀)。此外，XOR電路並不限於2個輸入，可以為3個輸入以上，例如也可以通過一個XOR電路進行從AND電路10a～10p輸出的數據塊的XOR運算。

(控制電路7的一個例子)

圖6是表示控制電路的一個例子的圖。

為了說明控制電路7與前述的編碼電路8的連接，對編碼電路8的一部分也進行圖示。

此外，在圖6中，對於進行編碼處理的控制的部分以外省略圖示。

控制電路7具有主控制電路13。主控制電路13具有加法器14、寄存器15、編碼矩陣保持部16、比較電路17、寄存器18、加法器19。並且，控制電路7具有寄存器20、21。

加法器14例如具有保持1的觸發器，使保持在寄存器15中的地址自加1(+1)。

寄存器15對BRAMm0～m15的寫入地址或讀出地址進行保持，另外，將保持的寫入地址或讀出地址經由輸入端子P3並輸出給BRAMm0～m15。寄存器15與未圖示的時鐘信號同步地對在保持的地址上通過加法器14進行+1加法所得的地址進行保持。

編碼矩陣保持部16例如具有多個寄存器，儲存RPS編碼矩陣。

圖7是表示RPS編碼矩陣的一個例子的圖。

圖7所示的RPS編碼矩陣是16行30列的矩陣。

基於RPS編碼處理的編碼數據按照RPS編碼矩陣的每個列向量而生成。RPS編碼矩陣的列編號為0～15的列向量在圖2的例子中，是生成編碼數據d0～d15時所使用的列向量。另外，RPS編碼矩陣的列編號為16～29的列向量在圖2的例子中，是生成冗餘編碼數據e16～e29時所使用的列向量。

列向量中的行與BRAMm0～m15對應。換句話說，在列向量中的某一行的值為「1」時，保持在與該行對應的BRAM中的數據塊被使用於XOR運算。

圖6的編碼矩陣保持部16根據從寄存器18輸出的列編號而將RPS編碼矩陣的列向量輸出給寄存器21。在初始狀態的情況下，保持在寄存器18中的值為0，所以編碼矩陣保持部16將列編號為0(j＝0)的列向量輸出給寄存器21。

比較電路17基於加法器14中的自加1次數來判定BRAMm0～m15中1數據塊量(例如1KB)的寫入是否結束，若1數據塊量的寫入終結束，則向寄存器18輸出設置信號。

寄存器18對RPS編碼矩陣的列編號進行保持。另外，寄存器18若接受比較電路17輸出的設置信號，則與未圖示的時鐘信號同步地對在保持的列編號上通過加法器19進行+1加法所得的列編號的值。

加法器19例如具有保持1的觸發器，使保持在寄存器18中的列編號自加1。

寄存器20若能夠進行向BRAMm0～m15的寫入，則對由主控制電路13內的未圖示的WE信號生成部生成的WE信號進行保持。另外，寄存器20將保持的WE信號經由輸入端子P4輸出給BRAMm0～15。

寄存器21將保持的RPS編碼矩陣的列向量的各值經由輸入端子P5輸出給AND電路10a～10p。例如列向量的第一行的值向AND電路10a輸入，第二行的值向AND電路10b輸入。

此外，根據本實施方式的編碼電路8包含在FPGA6B內，但也可以通過ASIC(Application Specific Integrated Circuit：專用集成電路)等來實現。

(RPS編碼處理的一個例子)

以下，對由編碼電路8進行的RPS編碼處理的一個例子進行說明。

圖8是表示RPS編碼處理的一個例子的流程的流程圖。

首先，進行向BRAMm0～m15的數據塊的寫入(步驟S1)。在步驟S1的處理中，控制電路7斷言WE信號，向BRAMm0～15供給寫入地址。而且，BRAMm0～m15從存儲器晶片6A經由存儲控制器6B2寫入被分割成固定尺寸的16個數據塊。

另外，主控制電路13將列編號j設定為0(步驟S2)。在步驟S2的處理中，主控制電路13的寄存器18的初始值被設定為0。

接下來，控制電路7將RPS編碼矩陣的列編號j的列向量的各值輸入給AND電路10a～10p(步驟S3)。在步驟S3的處理中，圖6所示那樣的寄存器21經由輸入端子P5將保持的RPS編碼的列編號j的列向量的各值輸入給AND電路10a～10p。

例如列編號j的列向量的第一行的值依次向AND電路10a輸入，第二行的值依次向AND電路10b輸入。此時，AND電路10a～10p進行列編號j的列向量的各值和BRAMm0～15的數據塊的AND運算，並將其運算結果輸出給XOR電路11a～11h。由此，AND電路10a～10p根據列向量的成為「1」的行的值來選擇保持在BRAMm0～15中的數據塊，並輸出給XOR電路11a～11h。例如在圖7所示的RPS編碼矩陣的列編號為0的列向量(j＝0)被輸入到AND電路10a～10p的情況下，由於僅第一行的值為「1」，所以輸入第一行的值的AND電路10a選擇BRAMm0的數據塊並輸出。

之後，編碼電路8進行XOR運算(步驟S4)。在步驟S4的處理中，通過XOR電路11a～11h進行使用了保持在BRAMm0～m15中的數據塊的XOR運算。

對於列編號j為0～15的各列向量，某一行的值為1，其它的行的值為0。在這樣的列向量被輸入到輸入端子P5時，從具有上述那樣的連接關係的XOR電路11a～11o的最後級的XOR電路11o輸出保持在與值為1的行對應的BRAM中的數據塊本身。

對於列編號為16～29的各列向量，多個行的值為1。在這樣的列向量被輸入到輸入端子P5時，從具有上述那樣的連接關係的XOR電路11a～11o的最後級的XOR電路11o輸出從AND電路10a～10p的任意2個以上輸出的多個數據塊的XOR運算結果。

接下來，主控制電路13判定列編號j是否達到最大值的29(步驟S5)，在列編號j小於29的期間，通過加法器19使列編號j進行+1(步驟S6)。步驟S6之後，重複從步驟S3的處理。

另外，在列編號j達到29的情況下，與1數據塊有關的RPS編碼處理完成。在編碼電路8進行與下一個數據塊有關的RPS編碼處理時，重複從步驟S1的處理。

之後，從編碼電路8輸出的編碼數據以及冗餘編碼數據經過通信處理電路6B3的處理等而作為數據包被轉送。另外，此時，使用於編碼的列向量被追加至該數據包報頭，並與編碼數據以及冗餘編碼數據一起被轉送。

如以上那樣，根據本實施方式的編碼電路8暫時由BRAMm0～m15中保持各數據塊，並基於列向量的值由AND電路10a～10p選擇使用於運算的數據塊並由XOR電路11a～11o進行XOR運算。通過這樣的並列化處理，在進行很多的XOR運算的RPS編碼處理等中，提高運算處理的效率，實現高速的運算(編碼處理)。

此外，在編碼電路8中，在使用64位×512位元組的BRAMm0～m15的情況下，如果是1KB的數據塊，則BRAMm0～m15能夠分別保持四個量的數據塊。由此，BRAMm0～m15能夠連續地向寄存器9a～9p輸入四個量的數據塊，所以編碼處理的處理能力進一步提高。而且，通過將BRAMm0～m15選為寫入和讀出能夠同時執行的雙埠存儲器，能夠隱瞞向BRAM寫入新的數據塊的時間，所以能夠進一步提高處理能力。

接下來，對解碼處理的一個例子進行說明。

(解碼處理的一個例子)

圖9是說明針對通過RPS編碼處理所得到的編碼數據的解碼處理的一個例子的圖。

在圖9中示出對從前述的編碼電路8經由網絡發送到解碼電路(參照圖10)的數據包所包含的編碼數據d0～d15以及冗餘編碼數據e0～e13進行解碼的樣子。

在解碼電路(參照圖10)中，參照接收到的數據包的報頭，從報頭提取編碼所使用的數據塊的組合信息(RPS編碼矩陣的列向量)。

由於編碼數據d0、d1、d3～d15相當於作為數據塊的塊b0、b1、b3～b15，所以保持原樣被輸出。

在圖9的例子中示出包括編碼數據d2的數據包消失的例子。解碼電路從能夠接收到的編碼數據以及冗餘編碼數據、和提取出的組合信息生成(解碼)消失的數據包的塊b2。例如塊b2如圖9所示，通過編碼數據d0、d1、d3、…、d15、冗餘編碼數據e0的XOR運算而生成。

這樣，即使解碼電路進行XOR運算，電路結構也與編碼電路8同樣。

接下來，使用圖10，對進行解碼處理時使用的解碼電路進行說明。此外，解碼電路例如與編碼電路8一起包含在圖3所示的FPGA6B內。控制解碼電路的控制電路能夠通過與圖6所示那樣的控制電路7同樣的電路來實現。

(解碼電路的一個例子)

圖10是表示根據第二實施方式的解碼電路的一個例子的圖。

解碼電路8a具有BRAMn0、n1、n2、n3、…、n26、n27、n28、n29、寄存器ra0、ra1、ra2、ra3、…、ra26、ra27、ra28、ra29。解碼電路8a還具有AND電路a0、a1、a2、a3、…、a26、a27、a28、a29、XOR電路部22、輸入端子P13～P15、和輸出端子P16。

對輸入端子P13輸入能夠使得寫入BRAMn0～n29的編碼數據等的WE信號。

對輸入端子P14輸入BRAMn0～n29寫入編碼數據等時的寫入地址、BRAMn0～n29讀出編碼數據等並輸出給AND電路a0～a29時的讀出地址。

對輸入端子P15輸入向AND電路a0～a29供給的後述的解碼向量的各值。

BRAMn0～n29若經由輸入端子P13、P14輸入寫入地址、WE信號，則將接收到的編碼數據等分別1塊1塊地寫入並保持。另外，BRAMn0～n29若經由輸入端子P13輸入讀出地址，則分別將保持的編碼數據等例如各64位地輸出給寄存器ra0～ra29。

BRAMn0～n29與編碼電路8輸出的30個數據塊(編碼數據)即，編碼數據d0～d15和冗餘編碼數據e0～e13對應，有30個。寄存器ra0～ra29、AND電路a0～a29也同樣。

寄存器ra0～ra29具有與圖5所示的寄存器9a～9p同樣的功能。

AND電路a0～a29與圖5所示的AND電路10a～10p同樣地作為選擇電路發揮作用。AND電路a0～a29分別進行BRAMn0～n29輸出的編碼數據或者冗餘編碼數據和從輸入端子P5輸入的解碼向量(作為選擇信號發揮作用)的各值的AND運算。而且，AND電路a0～a29將其運算結果輸出給XOR電路部22。此時，AND電路a0～a29分別根據經由輸入端子P15輸入的解碼向量(列向量)成為「1」的行來選擇BRAMn0～n29的編碼數據或者冗餘編碼數據並輸出。

XOR電路部22省略圖示，但例如和圖5所示的編碼電路8同樣地成為多個XOR電路和寄存器連接成樹狀的電路。

XOR電路部22進行通過AND電路a0～a29所選擇並被輸入的編碼數據或者冗餘編碼數據的XOR運算，對原始的數據塊進行解碼。

輸出端子P16輸出解碼出的原始的數據塊。

以下，在說明解碼電路8a的動作前，先對使用於解碼處理的解碼向量的生成處理進行說明。

(解碼向量的生成處理例)

解碼向量例如由控制解碼電路8a的未圖示的控制電路生成。

每當生成解碼向量時，首先，生成以下那樣的接收編碼矩陣。

圖11是對接收編碼矩陣的生成例進行說明的圖。

另外，圖12是表示生成的接收編碼矩陣的一個例子的圖。

在包括通過RPS編碼處理編碼所得的數據(編碼數據或者冗餘編碼數據)的數據包的報頭包含RPS編碼矩陣的列向量。

例如接收側的控制電路每當接收上述那樣的數據包時，從報頭提取上述列向量，並從列編號＝0起按接收順序排列，從而生成圖12所示那樣的接收編碼矩陣。

圖12所示的接收編碼矩陣(16行16列)是在接收到16個數據包的時刻生成的。以下，將接收編碼矩陣的列向量例如使用列編號c表現為列向量D(c)，將列向量D(c)的第u行的值表現為要素[u]。

此外，圖12所示的「基向量」和「基向量候補」後述。

從上述那樣的接收編碼矩陣生成解碼向量。

解碼處理例如與作為1次的聯立方程式的解法而已知的高斯消元法相似。例如在1次的聯立方程式中的、作為解的係數的矩陣為A、作為解的列向量為X、作為常量的列向量為C時，1次的聯立方程式表現為AX＝C。而且，對於AX＝C，以矩陣A成為單位矩陣E的方式應用高斯消元法，求出EX＝C1，即，X＝C1。

在根據本實施方式的解碼處理中，接收編碼矩陣用矩陣A表示，原始的數據塊用列向量X表示，編碼數據或者冗餘編碼數據用列向量C表示。

此處，作為輸入給解碼電路8a的AND電路a0～a29的選擇信號發揮作用的解碼向量基於接收編碼矩陣，例如在控制解碼電路8a的未圖示的控制電路中例如以下那樣生成。

圖13是表示解碼向量的生成處理的一個例子的流程的流程圖。

首先，進行代入多個解碼向量的值的矩陣ops的初始化(步驟S10)。

矩陣ops的初始化通過計算矩陣ops的對角要素成為1、其它的要素成為0的單位矩陣來進行。另外，矩陣ops具有與接收編碼矩陣的列數數目相同的行數以及列數。

接下來，接收編碼矩陣的列編號c被設定為0(步驟S11)。列編號c是在後述的步驟S13的處理中，代入基向量或者基向量候補的列編號的變量。

之後，對接收編碼矩陣所包含的列向量，進行基向量、基向量候補的決定(步驟S12)。

基向量僅具有一個成為1的要素，還是相互正交的向量。另外，以下，將要素[u](行編號為u的值)成為1的基向量稱為要素[u]的基向量。在圖12所示的接收編碼矩陣的例子中，若將列編號c的列向量設為D[c]，則列編號c為0～12的列向量D(0)～D(12)分別被決定為要素[3]～[12]的基向量。

基向量候補是在接收編碼矩陣中不存在要素[u]的基向量的情況下，要素[u]成為1的列向量。例如在圖12所示的接收編碼矩陣中不存在要素[0]～[2]的基向量。因此，要素[0]成為1的列向量D(13)被決定為要素[0]的基向量候補，要素[2]成為1的列向量D(14)被決定為要素[2]的基向量候補。另外，要素[1]成為1的列向量D(15)被決定為要素[1]的基向量候補。

接下來，進行將接收編碼矩陣的列向量向基向量變換的處理(步驟S13)。

在步驟S13的處理中，首先，在接收編碼矩陣中，在與基向量(或者基向量候補)的成為1的要素相同的行編號檢測要素成為1的列向量。而且，利用該要素和基向量的該要素的XOR運算結果更新檢測出的列向量的該要素。由於1和1的XOR運算結果為0，所以檢測出的列向量的該要素成為0。通過在接收編碼矩陣的各基向量(或者基向量候補)中重複這樣的處理，從而將接收編碼矩陣的基向量候補變換為基向量。

圖14是表示被更新的接收編碼矩陣的一個例子的圖。

通過步驟S13的處理，作為圖12所示的基向量候補的列向量D(13)～(15)如圖14所示那樣成為要素[0]～[1]的基向量。

另外，在上述的步驟S13的處理中，在將接收編碼矩陣的基向量候補變換為基向量時的XOR運算處理結果被代入到矩陣ops的各要素時，例如生成以下那樣的矩陣ops。

圖15是表示矩陣ops的一個例子的圖。

在矩陣ops的各要素中代入將接收編碼矩陣的基向量候補向基向量變換時的、XOR運算結果。以下，將矩陣ops的列編號i的列向量記載為列向量op(i)。

在圖12所示的接收編碼矩陣中，為了將列向量D(13)～D(15)變換為基向量，而進行上述那樣的基於XOR運算的更新處理。通過該XOR運算結果，矩陣ops的列向量op(13)～(15)在矩陣的對角要素以外具有成為1的要素。

該矩陣ops的列向量用作解碼向量。

圖16是表示矩陣ops的列向量(解碼向量)與通過該列向量解碼的數據塊的關係的一個例子的圖。

此外，在圖16中，為了便於說明，圖15所示的矩陣ops的列向量op(0)～op(15)的各個用32位的2進位表現。

列向量op(0)～op(15)的右端的要素是位0，與列向量op(0)～op(15)的第一行的要素對應。

如上述那樣，矩陣ops的列向量op(0)～op(15)的值成為將對應的列編號的接收編碼矩陣的列向量向基向量變更時的XOR運算結果的值。

通過將這樣的矩陣ops的列向量用作解碼向量，在解碼電路8a中，在編碼數據或者冗餘編碼數據間，進行與將接收編碼矩陣向基向量變換時的XOR運算同樣的處理。

通過矩陣ops的列向量op(0)～op(15)能夠解碼的數據塊同與該列向量op(0)～op(15)相同的列編號的更新後的接收編碼矩陣的基向量的成為1的要素的行編號對應。

另外，此處，由此接收編碼矩陣從編碼矩陣(圖7)的列向量生成，所以接收編碼矩陣的第一～第十六行的各要素與編碼矩陣同樣地同儲存有數據塊的BRAMm0～m15對應。即，通過矩陣ops的列向量解碼出的數據塊成為保持在與該列向量相同的列編號的、更新後的接收編碼矩陣的基向量的成為1的要素的行編號對應的BRAM中的數據塊。

例如在使用列向量op(2)對數據塊進行解碼對情況下，在更新後的接收編碼矩陣(圖14)中，成為與矩陣ops的列向量op(2)相同的列編號的列向量是列向量D(2)。另外，由於列向量D(2)是要素[5]為1的基向量，所以儲存在與接收編碼矩陣的行編號5對應的BRAMm5中的塊b5被解碼。

在使用列向量op(15)對數據塊進行解碼的情況下，在更新後的接收編碼矩陣(圖14)中，成為與矩陣ops的列向量op(15)相同的列編號的列向量是列向量D(15)。另外，由於列向量D(15)是要素[2]為1的基向量，所以儲存在與接收編碼矩陣的行編號2對應的BRAMm2中的塊b2被解碼。

此外，在數據包通信中，在傳送路徑上消失的編碼數據少的情況下，也能夠預先計算解碼向量，並儲存在控制解碼電路8a的未圖示的控制電路內的存儲部中。

(解碼電路8a的動作)

圖10所示那樣的解碼電路8a在多個BRAMn0～n29保持各數據塊(編碼數據(也包括冗餘編碼數據))，並基於上述那樣的解碼向量的值由AND電路a0～a29選擇使用於運算的數據塊。而且，選出的數據塊間的XOR運算由XOR電路部22進行。通過這樣的並列化處理，在進行很多的XOR運算的解碼處理中，提高運算處理的效率，實現高速的運算。

此外，在通過解碼電路8a使原始的數據塊全部再現(解碼)的情況下，包括解碼電路8a的接收側的裝置可以對發送側的裝置發送解碼完成信號。例如沒有數據包的丟失的情況下，若包括編碼數據d0～d15的多個數據包的接收完成，則接收側的裝置將解碼完成信號發送給發送側的裝置。在發送側的裝置中，在接收到解碼完成信號的時刻，使圖8所示那樣的編碼電路8中的編碼處理停止。由此，關於圖7所示的那樣的RPS編碼矩陣的全部列向量，可以不進行XOR運算。

(變形例)

圖17、18是表示根據第二實施方式的編碼電路的變形例的圖。此外，圖17、18與圖5所示的編碼電路8的一部分對應。與編碼電路8同樣的要素附加與圖5相同的符號，省略其說明。

在圖17中，在XOR電路11a的輸出側連接有BRAM30。另外，在寄存器12a和BRAM30的輸出側連接有選擇器31。

BRAM30對XOR電路11a的XOR運算結果，即BRAMm0～m1的數據塊間的XOR運算結果進行保持。另外，選擇器31基於輸入的選擇信號來選擇寄存器12a和BRAM30中的任意一個並輸出。選擇信號例如從圖4所示的控制電路7供給。

在圖18中，在XOR電路11i的輸出側連接有BRAM32。另外，在寄存器12i和BRAM32的輸出側連接有選擇器33。

BRAM32對XOR電路11i的XOR運算結果，即BRAMm0～m3的數據塊間的XOR運算結果進行保持。另外，選擇器33基於輸入的選擇信號來選擇寄存器12i和BRAM32中的任意一個並輸出。選擇信號例如從圖4所示的控制電路7供給。

在圖17、18中，對在XOR電路11a、11i的輸出側設置BRAM30、32、選擇器31、33的例子進行了說明，但同樣地也能夠設置於其它的XOR電路11b～11h、11j～n的輸出側。

圖19是表示根據第二實施方式的編碼電路的變形例的圖。此外，圖19所示的編碼電路8b是在圖5所示的編碼電路8的一部分設置BRAM以及選擇器的電路。另外，與編碼電路8同樣的要素標註與圖5所示的要素相同的符號，省略其說明。

在圖19的編碼電路8b的XOR電路11a的輸出側連接有BRAM30。另外，在寄存器12a和BRAM30的輸出側連接有選擇器31。

BRAM30對XOR電路11a的XOR運算結果進行保持，另外，選擇器31基於輸入的信號選擇寄存器12a和BRAM30中的任意一個並輸出。由此，由於保持在BRAMm0和BRAMm1中的數據塊間的XOR運算結果被保持於BRAM30，所以能夠再次利用該XOR運算結果。

以下對使用了圖19所示的編碼電路8b的編碼處理的流程進行說明。

圖20是說明編碼處理的一個例子的流程的圖。

例如在列編號為0的列向量經由輸入端子P5輸入到編碼電路8b時，保持在BRAMm0和BRAMm1中的數據塊間的XOR運算結果被保持於BRAM30。在圖20所示的RPS編碼矩陣中，與基於列編號為0的列向量的保持在BRAMm0和BRAMm1中的數據塊間的XOR運算同樣的運算也在列編號為28的列向量中進行。

因此，也能夠在列編號為28的列向量的編碼數據生成時利用在列編號為0的列向量中保持在BRAM30中的XOR運算結果。此時，由於在列編號為27的列向量以下不使用BRAMm0～m2的數據，所以在列編號為27的列向量以下，能夠向BRAMm0～m2寫入下一個數據塊。由此，能夠提高編碼處理的處理能力。

此外，上述那樣的變形也同樣地能夠應用於圖10所示的解碼電路8a。

以上，作為進行XOR運算的運算電路的例子，說明了編碼電路、解碼電路，但並不限於這些。例如也能夠應用於如RAID(Redundant Arrays of Inexpensive Disks：獨立冗餘磁碟陣列)6等那樣進行多次的XOR運算(用於奇偶數據的計算)。

上述僅表示本發明的原理。並且，對本領域技術人員來說能夠進行大多的變形、變更，本發明並不限於上述所示、說明的正確的結構以及應用例，對應的全部的變形例以及等同物視為基於付上的權利要求以及其等同物的本發明的範圍。

符號說明

1…運算電路；2a～2p…選擇電路；3a～3o…XOR電路；M0～M15…存儲器；P1…輸入端子；P2…輸出端子。