快速全息編解碼方法
2023-11-01 23:28:22
專利名稱：快速全息編解碼方法
技術領域：
本發明涉及一種快速全息編解碼方法，適用於傳統的流媒體直播、點播以及利用P2P(端對端)技術進行流媒體直播等應用領域。
背景技術：
傳統流媒體直播或點播的簡要邏輯圖如附圖1所示，流媒體數據源經過通信部件被提交到通信網中，流媒體接收端經過通信部件接收相應的流媒體數據，流媒體接收端僅從流媒體數據源獲得數據。
利用P2P技術直播流媒體，與通常的流媒體直播不同之處在於流媒體接收端還會往外發送流媒體數據，所以，接收端不再是僅僅只從流媒體數據源獲得數據，接收端更多的數據來源於其他接收端，因而，此接收端更準確地應該被稱為收發端。P2P直播流媒體的簡要邏輯圖如附圖2所示，流媒體數據源經過通信部件被提交到通信網中，流媒體收發端經過通信部件，在接收流媒體數據的同時，也向其他收發端轉發流媒體數據。
無論是傳統流媒體直播或點播，還是利用P2P技術直播流媒體，如果數據在通信網絡中被丟失一部分，接收端都將聽到噪音或看到帶有馬賽克的圖像。
發明內容
1、發明目的本發明的目的是提供一種快速全息編解碼方法，它能夠簡化傳統的流媒體直播、點播以及利用P2P技術進行流媒體直播等應用中的數據傳輸控制，有效地保障數據的可靠傳輸，進而改善聲音和圖像的質量。
2、技術方案一種快速全息編解碼方法，其特徵是它包括編碼方法和解碼方法，其中編碼方法包括以下步驟(A)生成隨機矩陣，該矩陣的所有項都由0或1構成；(B)生成隨機數由上述步驟(A)中的矩陣的每一行，生成隨機數；(C)快速異或生成中間結果由上述步驟(A)中的矩陣的一行的各項，與信源數據相乘後再異或，生成中間結果；(D)組合生成編碼結果由上述步驟(B)與步驟(C)的結果組合，生成編碼結果；解碼方法包括以下步驟(E)拆分編碼結果與上述編碼步驟(D)中的「組合生成編碼結果」相對應，將編碼結果拆分；(F)快速異或求三角矩陣利用快速異或消去法，逐行消去求得三角矩陣；(G)快速異或求解利用快速異或消去法，逐行消去求得對角線矩陣，最終求得解碼結果。
在上述方法中，還可以包括網絡再編碼方法，其步驟是(H)生成隨機矩陣，該矩陣的所有項都由0或1構成；(I)快速異或生成結果由上述步驟(H)中的矩陣的一行的各項，與接收到的數據相乘後再異或，生成網絡再編碼結果。
下面再詳細描述本發明的使用方法。
(1)在傳統流媒體直播或點播中使用快速全息編解碼。
如附圖3所示，在傳統流媒體直播或點播系統中，流媒體數據被通信部件提交到通信網之前，增加快速全息編碼這一環節，即信源端先對這些數據進行快速全息編碼，然後，接收端對收到的數據進行快速全息解碼。由於信源端編碼後的每一塊數據都含有一部分的原始信息量，只要接收端接收到數據的塊數足夠，就可以解碼出完整的原始數據，其原因是沒有任何一塊數據是關鍵數據塊，接收端不會因為缺少關鍵數據塊而無法進行解碼。利用快速全息編解碼的好處在於途經通信網絡後如果部分數據被丟失，接收端仍然有可能還原出流媒體的原始數據，保障了數據的可靠傳輸，進而改善圖像和聲音的質量。
(2)在P2P流媒體直播中使用快速全息編解碼。
在P2P流媒體直播時，收發端必須要判斷出到何處(包括其他收發端或信源)去索取哪些數據塊，有效地做出這些判斷，是一個非常關鍵而又很複雜的工作。利用快速全息編解碼，可將上述工作簡化為收發端僅需要判斷出到何處(包括其他收發端或信源)去索取數據塊，而不需要關心具體索取哪些數據塊，大幅度降低了這步關鍵工作的複雜程度，讓整個P2P系統更加健壯，從而有效地保障數據的可靠傳輸，進而改善圖像和聲音的質量。如圖4所示，在使用P2P技術進行流媒體直播時，流媒體數據被通信部件提交到通信網之前，增加快速全息編碼這一環節即信源端先對這些數據進行快速全息編碼，然後，收發端對收到的數據進行快速全息解碼及網絡再編碼，得到解碼結果並將網絡再編碼的數據轉發出去。
3、有益效果本發明與現有技術相比，其顯著優點是利用快速全息編解碼，可以有效地簡化數據傳輸的控制、保障數據的可靠傳輸。快速全息編解碼中，「快速」是指進行編解碼時，主要使用微處理器能快速完成的異或運算而不需要使用很消耗微處理器時間的大數乘除運算，「全息」是指編碼輸出的每一個數據塊，都包含有全部原始數據塊的一部分信息量。
四
圖1是傳統流媒體直播或點播的簡要邏輯圖。
圖2是P2P直播流媒體的簡要邏輯圖。
圖3是在傳統流媒體直播或點播中使用快速全息編解碼器的簡要邏輯圖。
圖4是在P2P流媒體直播中使用快速全息編解碼器的簡要邏輯圖。
五具體實施例方式
如圖3、圖4所示的快速全息編解碼方法(即稱快速全息編解碼器)，主要是一個功能模塊，可以採用軟體或硬體的方法實現。它包括快速全息編碼、快速全息解碼和快速全息網絡再編碼三部分，此三部分的實現步驟如下詳述。
為便於描述，我們統稱流媒體數據源為信源，並假設一部分信源由數據塊X1、X2、X3、……、Xm構成，小寫英文字母m、n、k、s、t、v等為符號下標，是自然數，並且n大於或等於m。
1、快速全息編碼的實現方法。
(1)生成隨機矩陣A如下矩陣A中的數據A11、A12、……A1m、……Ak1、Ak2、Ak3、……Akm、……An1、An2、An3、……Anm，隨機選擇為0或為1。
A=A11A12A13......A1mA21A22A23......A2m......Ak1Ak2Ak3......Akm......Am1Am2Am3......Amm......An1An2An3......Anm]]>(2)生成隨機數Ak由於A11、A12、A13、……、Anm只為0或1，所以，可用一個m位二進位數Ak來表示矩陣A的第k行的信息。比如，Ak的最高位為Ak1、次高位為Ak2、……最低位為Akm，例如，當A11＝1、A12＝1、A13＝0、……A1m＝1時，A1為二進位數110……1。
(3)快速異或生成中間結果PkPk＝(Ak1*X1)xor(Ak2*X2)xor(Ak3*X3)xor…xor(Akm*Xm)其中xor為異或運算符，由於Ak1、Ak2、Ak3、……Akm只能為0或1，所以上述運算演變成微處理器能快速完成的異或運算。例如，A11＝1、A12＝0、A13＝1、A14＝0、A15直到A1(m-1)都為0、A1m＝1，則P1＝X1 xor X3 xor Xm。
(4)組合生成編碼結果Yk將Ak與Pk組合，生產一個新的數據塊Yk。例如，A1為二進位數0001，P1為二進位數01011111，則可組合成數據塊Y1＝000101011111。
快速全息編碼具體的實現方法第一步按上述「生成隨機矩陣A」的方法，隨機設置上述矩陣A中的數據A11、A12、……Anm為0或者1，為便於快速全息解碼，要保證隨機算法的有效性。
第二步按上述「生成隨機數Ak」的方法，生成n個m位二進位數據A1、A2、A3、……An。
第三步按上述「快速異或生成中間結果Pk」的方法，生成n個數據塊P1、P2、P3、……Pn。
第四步按上述「組合生成編碼結果Yk」的方法，生成n個數據塊Y1、Y2、Y3、……Yn。
上述第四步的輸出，即為快速全息編碼的編碼輸出結果。信源的m塊數據X1、X2、X3、……、Xm，經過快速全息編碼後，輸出n塊數據Y1、Y2、Y3、……、Ym、……、Yn，輸出的數據塊個數n可以按需要多於輸入的數據塊個數m。
2、快速全息解碼的實現方法。
發送端將m個原始信源數據塊X1、X2、X3、……、Xm，經過快速全息編碼得到n個編碼輸出結果Y1、Y2、Y3、……、Ym、……、Yn，並通過通信網絡將其發送到接收端，接收端收到Y1、Y2、Y3、……、Ys，由於通信網絡傳輸中可能丟失數據，所以，接收端接收到的數據塊個數s可能小於發送端發送的個數n，但為了解碼，要確保s大於或等於m。
(1)拆分編碼結果Yk與發送端相對應，接收端將Y1、Y2、Y3、……、Ys中的每個數據塊Yk拆成Ak和Pk，再將m位二進位數Ak拆為m個為0或1的值Ak1、Ak2、Ak3、……、Akm。由A1、A2、A3、……、As及P1、P2、P3、……、Ps可構成如下兩個矩陣。
A11A12A13......A1mA21A22A23......A2m......Ak1Ak2Ak3......Akm......Am1Am2Am3......Amm......As1As2As3......AsmP1P2......Pk......Pm......Ps]]>(2)快速異或求三角矩陣採用微處理器能迅速完成的異或運算，對上述兩個矩陣的每行進行相同的處理如下從A11、A21、……、Ak1、……、Am1、……、As1中，任選一個值為1的數，並將其所對應的行，排在第1行。然後，第k行的Ak1如果為0，則直接排在第k行，第k行的Ak1如果為1，則將第k行與第1行異或後，再排於第k行，得到如下兩個矩陣1B12B13......B1m0B22B23......B2m......0Bk2Bk3......Bkm......0Bm2Bm3......Bmm......0Bs2Bs3......BsmQ1Q2......Qk......Qm......Qs]]>從B22、B32、……、Bk2、……、Bm2、……、Bs2中，任選一個值為1的數，並將其所對應的行，排到第2行。然後，第k行的Bk2如果為0，則直接排在第k行，第k行的Bk2如果為1，則將第k行與第2行異或後，再排於第k行，得到如下兩個矩陣1C12C13......C1m01C23......C2m......00Ck3......Ckm......00Cm3......Cmm......00Cs3......CsmR1R2......Rk......Rm......Rs]]>重複上述步驟共m次，左邊矩陣中第m行僅有第m個項為1，其餘均為0，丟棄多餘的行(其道理類似於線性方程組中有些方程式之間可能是線性相關的，所以解出m元一次線性方程組所需要的方程式的個數s，有可能大於m)，最終得到如下兩個矩陣E和T，矩陣E為一個三角矩陣E=1E12E13......E1(m-1)E1m01E23......E2(m-1)E2m001......000......1Ek(K+1)......Ek(m-1)Ekm......000......01E(m-1)m000......001T=T1T2T3......Tk......T(m-1)Tm]]>(3)快速異或求解採用微處理器能迅速完成的異或運算，對上述兩個矩陣E和T的每行進行相同的處理如下對於上述兩個矩陣的倒數第2行，如果E(m-1)m＝1，則倒數第2行與倒數第1行異或後，再排於倒數第2行；如果E(m-1)m＝0，倒數第2行保持不變，得到如下兩個矩陣1F12F13......F1(m-1)E1m01F23......F2(m-1)E2m001......000......1Fk(k+1)......Fk(m-1)Fkm......000......010000......001U1U2U3......Uk......U(m-1)Um]]>採用異或運算，重複上述類似步驟，最後可以得到如下兩個矩陣H和WH=100......0000010......00000010......0000......000......1......000......000......010000......001W=W1W2W3......Wk......W(m-1)Wm]]>從而，解出m個變元X1、X2、X3、……、Xm的值為X1＝W1、X2＝W2、X3＝W3、……、Xm＝Wm。
快速全息解碼具體的實現方法第一步按上述「拆分編碼結果Yk」的方法，將接收到的結果Yk拆分成Ak和Pk，並得到兩個矩陣。
第二步按上述「快速異或求三角矩陣」的方法，生成兩個矩陣E和T，其中，矩陣E為三角矩陣。
第三步按上述「快速異或求解」的方法，生成矩陣W，從而解出X1＝W1、X2＝W2、X3＝W3、……、Xm＝Wm。
上述第三步的輸出結果X1、X2、X3、……、Xm，即為快速全息解碼結果。接收端利用接收到的s個數據塊Y1、Y2、Y3、……、Ys，還原出m塊原始信源數據X1、X2、X3、……、Xm，由於第一步拆分Yk得到的矩陣的各行，可能有些行是線性相關的，所以，解碼所需的數據塊個數s可能大於原始信源的數據塊個數m。
3、快速全息網絡再編碼的實現方法。
收發端接收到發送端(包括其他收發端或信源)發出的若干個編碼輸出結果Y1、Y2、Y3、……、Yt，在轉發之前，收發端需要對其再編碼後，才能將結果轉發到通信網絡中，此再編碼過程稱為網絡再編碼。
(1)生成隨機矩陣Q如下矩陣Q中的數據Q11、Q12、……Q1t、……Qk1、Qk2、Qk3、……Qkt、……Qv1、Qv2、Qv3、……Qvt，隨機選擇為0或1。
Q=Q11Q12Q13......Q1tQ21Q22Q23......Q2t......Qk1Qk2Qk3......Qkt......Qt1Qt2Qt3......Qtt......Qv1Qv2Qv3......Qvt]]>(2)快速異或生成編碼結果ZkZk＝(Qk1*Y1)xor(Qk2*Y2)xor(Qk3*Y3)xor…xor(Qkt*Yt)其中xor為異或運算符，由於Qk1、Qk2、Qk3、……Qkt只能為0或1，所以上述運算演變成微處理器能快速完成的異或運算。例如，Q11＝1、Q12＝0、Q13＝1、Q14＝0、Q15直到Q1(t-1)都為0、Q1t＝1，則Z1＝Y1 xor Y3 xor Yt。
快速全息網絡再編碼具體的實現方法第一步按上述「生成隨機矩陣Q」的方法，隨機設置上述矩陣Q中的數據Q11、Q12、……Qvt為0或者1，為便於快速全息解碼，要保證隨機算法的有效性。
第二步按上述「快速異或生成編碼結果Zk」的方法，生成v個數據塊Z1、Z2、Z3、……、Zv。
上述第二步的輸出，即為快速全息網絡再編碼的輸出結果，輸出的數據塊個數v可以按需要多於輸入的數據塊個數t。
上述快速全息編碼、解碼、網絡再編碼，主要是利用了微處理器能迅速完成的異或運算，而沒有使用很消耗微處理器時間的大數乘除運算，從而保證了編解碼的高效性。
權利要求
1.一種快速全息編解碼方法，其特徵是它包括編碼方法和解碼方法，其中編碼方法包括以下步驟(A)生成隨機矩陣，該矩陣的所有項都由0或1構成；(B)生成隨機數由上述步驟(A)中的矩陣的每一行，生成隨機數；(C)快速異或生成中間結果由上述步驟(A)中的矩陣的一行的各項，與信源數據相乘後再異或，生成中間結果；(D)組合生成編碼結果由上述步驟(B)與步驟(C)的結果組合，生成編碼結果；解碼方法包括以下步驟(E)拆分編碼結果與上述編碼步驟(D)中的「組合生成編碼結果」相對應，將編碼結果拆分；(F)快速異或求三角矩陣利用快速異或消去法，逐行消去求得三角矩陣；(G)快速異或求解利用快速異或消去法，逐行消去求得對角線矩陣，最終求得解碼結果。
2.根據權利要求1所述的快速全息編解碼方法，其特徵是它還可包括網絡再編碼方法，其步驟是(H)生成隨機矩陣，該矩陣的所有項都由0或1構成；(I)快速異或生成結果由上述步驟(H)中的矩陣的一行的各項，與接收到的數據相乘後再異或，生成網絡再編碼結果。
全文摘要
本發明公開一種快速全息編解碼方法，適用於傳統的流媒體直播、點播以及利用P2P技術進行流媒體直播等應用領域，在這些應用領域中使用該快速全息編解碼，將有效地簡化數據傳輸的控制，保障數據的可靠傳輸，進而改善聲音和圖像的質量，克服了以往流媒體直播或點播應用中，當數據被丟失一部分之後，出現噪音及馬賽克圖像的難題。本發明包括編碼方法和解碼方法，還可包括網絡再編碼方法，詳細描述了如何在傳統的流媒體直播及點播應用中使用該快速全息編解碼，如何在利用P2P技術進行流媒體直播的應用中使用該快速全息編解碼。
文檔編號H04N7/173GK1738425SQ200510094180
公開日2006年2月22日 申請日期2005年9月1日 優先權日2005年9月1日
發明者趙振平, 汪渝波, 鄒暢根 申請人:南京信風軟體有限公司