一種差錯控制方法和系統的製作方法

2023-09-22 20:24:10

專利名稱：一種差錯控制方法和系統的製作方法
技術領域：
本發明涉及一種差錯控制方法和系統，適用於通信、存儲等領域。

背景技術：
隨著寬帶網絡及視頻業務的發展，組播得到了廣闊的應用，例如IPTV。組播應用中有大量的用戶接收共同的數據源，標準的組播協議是不帶反饋的，這就帶來新的問題如果網絡上出現丟包，由於每個用戶丟失的數據都可能不一樣，為此需要一種有效的恢復機制，無論用戶丟失哪些數據包，都能將丟失的數據恢復。同樣，在存儲領域也存在如何將丟失的數據進行恢復的問題。


發明內容
發明目的本發明的目的是提供一種差錯控制方法和實現該方法的系統，有效地將丟失的數據恢復，提高數據完整性。
技術方案一種差錯控制方法，包括生成冗餘包的方法和信源恢復的方法，其中生成冗餘包的方法包括以下步驟 (1)構造編碼係數矩陣A 假設有n個信源X1、X2、X3......Xn，m為需要生成的冗餘包的數量，選一個數域P，保證每個信源Xj都在數域P內，在數域P中任取(n+m)個不同的值K1、K2、K3......Kn、L1、L2......Lm，取矩陣K和L如下 由於矩陣K是範德蒙矩陣(Vandermonde Matrix)，所以矩陣K一定存在逆矩陣K-1。將矩陣L乘以矩陣K-1，得到編碼係數矩陣A如下 步驟(1)每步數學運算都採用數域P內的運算。
(2)計算冗餘包 取信源矩陣X如下 將編碼係數矩陣A乘以信源矩陣X，得到冗餘包矩陣Y如下 Y1、Y2、Y3......Ym即為m個冗餘包。步驟(2)每步數學運算都採用與步驟(1)相同的數域P內的運算。
將矩陣K的所有行及矩陣L的所有行，組成矩陣F如下 則如下等式成立，等式右邊由n個信源及m個冗餘包構成。
等式右邊取任意n行，等式左邊矩陣F也取相應的n行，上述等式仍然成立。等式右邊的任意n行，實質上是信源個數加冗餘包個數等於n的任意n個信息，將它記為矩陣G，等式左邊矩陣F取相應的n行後得到矩陣H，則得到如下等式 H*K-1*X＝G 由於H也是範德蒙矩陣，所以矩陣H一定存在逆矩陣H-1，將上等式兩邊都左乘矩陣H-1得到如下等式 K-1*X＝H-1*G 再將上等式兩邊都左乘矩陣K得到如下等式 X＝K*H-1*G 因而理論上，從n個信源及m個冗餘包中任取n個信息都可以恢復出n個信源，這是本發明的數學原理。
發信端將n個信源及m個冗餘包發送往收信端，當收信端收到的信源個數r小於n時，信源恢復的方法包括以下步驟 (3)構造解碼係數矩陣B 假設收到Xf、Xg......Xh共r個信源，其中f＜g＜……＜h，收到t個冗餘包，當t大於(n-r)時任取(n-r)個冗餘包，當t小於或等於(n-r)時取所有的冗餘包，這些冗餘包記為Yu、Yv......Yw，其中u＜v＜……＜w，取矩陣B第1行的第f列為1、其他(n-1)列為0；矩陣B第2行的第g列為1、其他(n-1)列為0......矩陣B第r行的第h列為1、其他(n-1)列為0；矩陣B第(r+1)行為步驟(1)係數矩陣A的第u行；矩陣B第(r+2)行為步驟(1)係數矩陣A的第v行......矩陣B最後1行為步驟(1)係數矩陣A的第w行，構成解碼係數矩陣B如下 (4)恢復出信源X 當t大於(n-r)時任取(n-r)個冗餘包，當t小於或等於(n-r)時取所有的冗餘包，得到如下等式 當t大於或等於(n-r)時，前面已經證明解碼係數矩陣B是一個範德蒙矩陣H與另一個範德蒙矩陣K的逆的乘積並且上述等式必定有解，可採用解(n-r)元1次方程組的解法解出(n-r)個未收到的信源Xj。當t小於(n-r)時，由於等式個數小於變元數，因而只能部分解出(n-r)個信源。步驟(4)每步數學運算都採用與步驟(1)相同的數域P內的運算。
上面描述了生成冗餘包Y及將信源X恢復的差錯控制方法，下面描述如何實現該差錯控制方法的系統，包括以下內容 (a)上述步驟(1)、(2)、(4)中的數域P採用擴展伽羅瓦2q域(Extended Galois Field 2q)。
(b)事先按上述步驟(1)算好編碼係數矩陣A，並將它存儲在發信端和收信端的存儲器上。
(c)發信端將信源Xj按固定的規則切成s個片段Xj1、Xj2、Xj3......Xjs，保證每個片段的值都在上述擴展伽羅瓦2q域內，信源Xj切片後得到如下信源矩陣X 發信端利用CPU或ASIC按如下等式生成冗餘包，冗餘包Yi由Yi1、Yi2、Yi3......Yis構成。將n個信源Xj及m個冗餘包Yi發送往收信端。
(d)當收信端收到的信源數r小於n時，取r個的信源及(n-r)個冗餘包，並將信源Xj及冗餘包Yi按與(c)同樣的規則切成s個片段。利用CPU或ASIC按上述步驟(3)和(4)的方法恢復出信源。信源Xj及冗餘Yi包切片後，步驟(4)恢復信源的等式如下 有益效果本發明與現有技術相比，其顯著優點是從n個信源及m個冗餘包中任取n個數據包，都一定能恢復出n個信源，保證了冗餘包信息量的最大化。採用擴展伽羅瓦2q域內的運算，在減少運算量的同時還能保證信道容量得到最有效的利用。本發明的方法是資訊理論香農定律在實踐應用中的最優化方法之一，具有很高的可用性。
在組播應用如IPTV中使用本發明的方法和系統，能有效地將丟失的組播數據恢復，完美地解決組播應用中當數據被丟失一部分之後出現的故障例如IPTV的噪音及圖像停頓或馬賽克。



圖1是冗餘包生成單元的簡要邏輯圖。
圖2是信源恢復單元的簡要邏輯圖。

具體實施例方式 上述技術方案中的數域P，可採用任何無限數域或有限數域，無限數域如實數域、有理數域，有限數域如基本伽羅瓦域，在這些數域中的運算如在實數域內的運算，5050是個巨大的數，需要增大存儲空間，也不利於有效地利用信道容量。採用有限域中的擴展伽羅瓦pq域，對於p取2，則任何運算的結果都不會要求更多的存儲空間。具體實施本發明描述的方法時，一般選用擴展伽羅瓦2q域。由於2q域內運算略難理解，雖然它在一些數學和計算機書籍中有詳細描述，但這裡還是舉例說明28域內的運算以便於理解。域2內有兩個值0、1，域2內的加法運算0+0＝0，0+1＝1，1+0＝1，1+1＝0，乘法運算0*0＝0，0*1＝0，1*0＝0，1*1＝1。28域內有256個值0、1、2、3......255。x8域內的任一值都可用包含x0、x1、x2、x3、x4、x5、x6、x7的多項式構成，例如x＝2時在x8域內，249＝x0+x3+x4+x5+x6+x7，30＝x1+x2+x3+x4，對249和30進行加法運算過程如下
即在28域內249+30＝231，從運算過程可知，28域內的加法運算，實質就是將兩個數進行2進位的異或運算。當x＝2時在x8域內選取一個包含x8的質多項式，例如取質多項式Z(x)＝1+x+x3+x4+x8，它無法被拆成任何其他兩個多項式的乘積。28域內兩個數相乘的結果是將其對應的兩個多項式相乘後除以質多項式而得到的餘數多項式所代表的值，例如28域內249*30的計算方法是先將249對應的多項式[x0+x3+x4+x5+x6+x7]與30對應的多項[x1+x2+x3+x4]相乘，得到積多項式[x1+x2+x3+x6+x9+x11]，乘法運算如下
將積多項式除以Z(x)得到商多項式[x3+x]及餘數多項式[x7+x5]，餘數多項式[x7+x5]對應的值為160，計算過程如下
因而在28域取上述質多項Z(x)時，249*30＝160，乘法運算有256*256種可能。由於28域的乘法運算量較大，在實際使用時可將28域內的所有可能的乘法運算事先計算好並存成一張256*256的乘法表，從而將乘運算過程轉化為查表過程。考慮到乘法交換律，28域內的乘法共有257*128種可能，為了減少存儲量也可僅存一張257*128的乘法表。28域內的值都可用1個Byte來表示，因而28域內運算在常用CPU系統中的開銷較小。
技術方案的實施例中，取擴展伽羅瓦28域，n＝64，m＝7，K1＝0、K2＝1、K3＝2......K64＝63，對應地信源為X1、X2、X3......X64；L1＝64、L2＝65......L7＝70，對應地冗餘包為Y1、Y2、Y3......Y7。
如何求範德蒙矩陣K的逆矩陣K-1，在許多數學書籍中都有描述，這裡不再敘述，28域內的加法運算採用2進位異或運算，28域內的乘法運算前面也已經描述過，利用28域內的加法和乘法，最後求得7行64列的編碼係數矩陣A＝L*K-1如下 矩陣A第1行的64列分別為118，48，2，204，197，55，235，181，54，91，92，15，232，137，25，200，63，164，162，165，60，13，29，226，212，202，56，73，74，187，249，41，173，183，122，245，158，178，134，193，111，231，176，159，36，163，175，104，45，174，133，14，152，189，64，217，42，229，98，53，3，22，40，191。
矩陣A第2行的64列分別為48，118，204，2，55，197，181，235，91，54，15，92，137，232，200，25，164，63，165，162，13，60，226，29，202，212，73，56，187，74，41，249，183，173，245，122，178，158，193，134，231，111，159，176，163，36，104，175，174，45，14，133，189，152，217，64，229，42，53，98，22，3，191，40。
矩陣A第3行的64列分別為2，204，118，48，235，181，197，55，92，15，54，91，25，200，232，137，162，165，63，164，29，226，60，13，56，73，212，202，249，41，74，187，122，245，173，183，134，193，158，178，176，159，111，231，175，104，36，163，133，14，45，174，64，217，152，189，98，53，42，229，40，191，3，22。
矩陣A第4行的64列分別為204，2，48，118，181，235，55，197，15，92，91，54，200，25，137，232，165，162，164，63，226，29，13，60，73，56，202，212，41，249，187，74，245，122，183，173，193，134，178，158，159，176，231，111，104，175，163，36，14，133，174，45，217，64，189，152，53，98，229，42，191，40，22，3。
矩陣A第5行的64列分別為197，55，235，181，118，48，2，204，232，137，25，200，54，91，92，15，60，13，29，226，63，164，162，165，74，187，249，41，212，202，56，73，158，178，134，193，173，183，122，245，36，163，175，104，111，231，176，159，152，189，64，217，45，174，133，14，3，22，40，191，42，229，98，53。
矩陣A第6行的64列分別為55，197，181，235，48，118，204，2，137，232，200，25，91，54，15，92，13，60，226，29，164，63，165，162，187，74，41，249，202，212，73，56，178，158，193，134，183，173，245，122，163，36，104，175，231，111，159，176，189，152，217，64，174，45，14，133，22，3，191，40，229，42，53，98。
矩陣A第7行的64列分別為235，181，197，55，2，204，118，48，25，200，232，137，92，15，54，91，29，226，60，13，162，165，63，164，249，41，74，187，56，73，212，202，134，193，158，178，122，245，173，183，175，104，36，163，176，159，111，231，64，217，152，189，133，14，45，174，40，191，3，22，98，53，42，229。
計算出編碼係數矩陣A之後，可求得冗餘包矩陣如下 Y＝A*X 假設收信端僅接收到信源X3、X4、X5......X62、X63，信源X1、X2及X64在傳輸過程中被丟失，同時收信端還收到冗餘包Y2、Y5、Y6、Y7，冗餘包Y1、Y3、Y4在傳輸過程中被丟失，則可構造解碼係數矩陣B如下
對於信源及冗餘包切片舉例如下，假設每個信源及冗餘包都由5個字符構成，則可將每個信源及冗餘包都切成5片，例如信源X3為字符串abcde，冗餘包Y2為字符串rstuv，X3切片後得到X31＝a，X32＝b，X33＝c，X34＝d，X35＝e，Y2切片後得到Y21＝r，Y22＝s，Y23＝t，Y24＝u，Y25＝v。收信端需要恢復出的信源X1、X2及X64相當於如下等式的未知數，由於X3、X4、X5......X63及Y2、Y5、Y6都已知，如下等式即成為5組3元1次方程組，解開這些方程組即得到信源X1、X2及X64，解方程過程中的數學運算仍採用上述28域內的運算。
圖1是冗餘包生成單元的簡要邏輯圖，由CPU或ASIC及存儲器等單元構成，在不易失存儲器中存儲編碼係數矩陣A及28域內的乘法表，由CPU或ASIC按技術方案的步驟(2)生成冗餘包。
圖2是信源恢復單元的簡要邏輯圖，由CPU或ASIC及存儲器等單元構成，在不易失存儲器中存儲編碼係數矩陣A及28域內的乘法表，由CPU或ASIC按技術方案的步驟(3)和(4)解出所有信源。
目前有些商用的組播應用例如IPTV僅使用1個UDP埠組播，為了與原有的系統兼容，使用本發明描述的新方法時可採用2個UDP埠，例如現有某套IPTV節目使用組播地址IP_M、埠Port_M，使用新方法時，這套IPTV節目的信源X也使用組播地址IP_M、埠Port_M，其冗餘包Y使用同樣的組播地址IP_M，但使用另一個埠Port_N，原有IPTV終端僅接收埠Port_M上的數據，使用本發明描述方法的新終端同時接收埠Port_M及Port_N上的數據，從而能保證新老終端都能正常工作。此外，為進一步增強組播的可靠性，組播接收端還可將信源恢復失敗的次數反饋到中央伺服器以進行通信質量評估，中央伺服器可隨信源恢復失敗率的增減動態指揮組播發信端增減冗餘包的個數。
權利要求
1、一種差錯控制方法，其特徵是該方法包括生成冗餘包的方法和信源恢復的方法，其中生成冗餘包的方法包括以下步驟
(1)構造編碼係數矩陣A
假設有n個信源X1、X2、X3......Xn，m為需要生成的冗餘包的數量，選一個數域P，保證每個信源Xj都在數域P內，在數域P中任取(n+m)個不同的值K1、K2、K3......Kn、L1、L2......Lm，取矩陣K和L如下
取K的逆矩陣K-1，將矩陣L乘以矩陣K-1，得到編碼係數矩陣A如下
步驟(1)每步數學運算都採用數域P內的運算；
(2)計算冗餘包
取信源矩陣X如下
將編碼係數矩陣A乘以信源矩陣X，得到冗餘包矩陣Y如下
Y1、Y2、Y3......Ym即為m個冗餘包；步驟(2)每步數學運算都採用與步驟(1)相同的數域P內的運算；
發信端將n個信源及m個冗餘包發送往收信端，當收信端收到的信源個數r小於n時，信源恢復的方法包括以下步驟
(3)構造解碼係數矩陣B
假設收到Xf、Xg......Xh共r個信源，其中f＜g＜……＜h，收到t個冗餘包，當t大於(n-r)時任取(n-r)個冗餘包，當t小於或等於(n-r)時取所有的冗餘包，這些冗餘包記為Yu、Yv......Yw，其中u＜v＜……＜w，取矩陣B第1行的第f列為1、其他(n-1)列為0；矩陣B第2行的第g列為1、其他(n-1)列為0......矩陣B第r行的第h列為1、其他(n-1)列為0；矩陣B第(r+1)行為步驟(1)編碼係數矩陣A的第u行；矩陣B第(r+2)行為步驟(1)編碼係數矩陣A的第v行......矩陣B最後1行為步驟(1)編碼係數矩陣A的第w行，構成解碼係數矩陣B如下
(4)恢復出信源X
當t大於(n-r)時任取(n-r)個冗餘包，當t小於或等於(n-r)時取所有的冗餘包，得到如下等式
當t大於或等於(n-r)時，利用上等式解出(n-r)個未收到的信源Xj；當t小於(n-r)時，利用上等式部分解出(n-r)個未收到的信源Xj；步驟(4)每步數學運算都採用與步驟(1)相同的數域P內的運算。
2、實現如權利要求1所述差錯控制方法的系統，其特徵是
(a)數域P採用擴展伽羅瓦2q域；
(b)事先算好編碼係數矩陣A，並將它保存在發信端和收信端；
(c)發信端將信源Xj按固定的規則切成s個片段，保證每個片段的值都在上述擴展伽羅瓦2q域內，利用CPU或ASIC生成冗餘包，然後將n個信源及m個冗餘包發送往收信端；
(d)當收信端收到的信源數r小於n時，取r個的信源及(n-r)個冗餘包，並按與(c)同樣的規則將信源Xj及冗餘包Yi切成s個片段，利用CPU或ASIC恢復出信源。
全文摘要
本發明公開了一種差錯控制方法和系統，適用於通信、存儲等領域，在這些領域中使本發明的方法或系統，可有效地將丟失的數據恢復，提高數據的完整性。本發明的方法包括生成編碼係數和冗餘包、生成解碼係數和恢復信源等步驟，發信端以n個信源生成m個冗餘包，將信源及冗餘包都發送往收信端，收信端收到的信源個數與冗餘包個數之和只要大於n，就能恢復出所有n個信源。本發明利用範德蒙矩陣及擴展伽羅瓦2q域內的運算，巧妙地實現了信息量最大化及運算量最小化。在多播及廣播通信中使用本發明的差錯控制方法或系統，可取得優良的效果。
文檔編號H04L1/22GK101404563SQ20081023451
公開日2009年4月8日 申請日期2008年11月20日 優先權日2008年11月20日
發明者呂曉雯, 劉怡梅, 玲 杜 申請人:呂曉雯, 劉怡梅, 玲 杜