生成與讀出可變長度代碼字數據流的方法和設備的製作方法
2023-05-20 19:53:11
專利名稱：生成與讀出可變長度代碼字數據流的方法和設備的製作方法
技術領域：
本發明涉及用可變長度代碼字進行的編碼，具體地說，是涉及生成與讀取傳輸中抗差錯能力強的具有可變長度代碼字的數據流。
例如，按照MPEG層3標準工作的現代音頻編碼或解碼方法能夠對音頻信號的數據率壓縮例如因數12，而不會使其質量明顯下降。為實現這種高數據率的縮減，對一個音頻信號進行採樣，以獲得一個時間離散的採樣值序列。如業內所知的，對該時間離散的採樣值序列取一窗口以便獲得有界的時間採樣值組。然後，一個時間窗採樣值組通過濾波器組(filter bank)、修正餘弦離散變換(MDCT)或其他適合的設備被轉換成頻率範圍，以便獲得整體上表示音頻信號的頻譜值，即在該頻率範圍內由時間離散的採樣值組確定的時間段。通常，通過MDCT生成相互間重迭50％的時間組值，並且該時間值組被轉換成頻率範圍，由於MDCT的特性，例如1024個時間離散的採樣值總是產生1024個頻譜值。
眾所周知，人的聽力取決於音頻信號本身的瞬間頻譜。這種依賴性屬於所謂的心理聽覺模式，通過該模式，在相當長的時間裡依據該瞬間頻譜對掩蔽閾值進行計算一直是可行的。掩蔽(masking)意指在例如相鄰的頻譜範圍，具有相對較高的能量的情況下，一個特定的單音或一個頻譜分量被掩蔽起來。為了儘可能接近地量化轉換之後出現的頻譜值，掩蔽的這一作法得到了應用。因此該目的一方面在於避免重新編碼的音頻信號中的可聽見的幹擾，另一方面在於使用儘可能少的位來編碼或者，在這一情況下，來量化音頻信號。由量化引起的幹擾，即量化噪聲，應當低於掩蔽閾值，因此，是聽不見的。根據已知的方法，對所謂的比例係數頻帶(scale factor bands)中的頻譜值進行分類，這種分類應與人耳的臨界頻帶，即頻率組相符。一個比例係數組中的頻譜值乘以一個比例係數以便對一個比例係數頻帶中的頻譜值進行整體換算。經比例係數換算的比例係數頻帶則被量化，以此生成經過量化的頻譜值。可以理解，比例係數頻帶的分組並非關鍵性的。然而，它卻在MPEG層3標準或者在MPEG 2 AAC標準(AAC＝先進音頻編碼)中得到應用。
數據縮減的一個根本的方面在於量化之後的平均信息量編碼。Huffman(霍夫曼)編碼通常用於平均信息量編碼。Huffman編碼被理解為它意味著用一個可變長度來進行編碼，即被編碼的值的代碼字的長度取決於它出現的概率。從邏輯上講，概率最大的字符被分配給最短的代碼，即最短的代碼字，以便通過Huffman編碼實現良好的冗餘縮減。一個公知的用一般長度進行編碼的例子是Morse代碼。
在音頻編碼領域，Huffman代碼用於對經過量化的頻譜值進行編碼。現代的音頻編碼器，例如根據MPEG 2 AAC標準工作的編碼器，使用不同的Huffman代碼表對量化的頻譜值進行編碼，而該代碼表是以逐段進行為基礎按照某些條件分配給該頻譜的。在這一過程中，總是把2個或4個頻譜值一起編碼於一個代碼字中。
根據MPEG 2 AAC的方法與根據MPEG層3的方法之間的一個差別是不同的比例係數頻帶，即不同的頻譜值，被分組歸入任意數量的頻譜段。對於AAC，一個頻譜段包括至少4個頻譜值，但最好是多於4個頻譜值。這些頻譜值的整個頻率範圍因此而被分成相臨的頻段，一個頻段表示一個頻帶，這樣，所有的頻段就共同覆蓋了由經轉換後的頻譜值合成的整個頻率範圍。
比如在MPEG層3方法中，一個頻段被分配給一個選自多個這種表格的所謂的「Huffman表」，以便實現最大的冗餘縮減。在AAC方法的通常含有1024個頻譜值的位流中，現在是按照頻率的上升順序排列的頻譜值的Huffman代碼字。每個頻段中使用的表上的信息以從屬信息的形式傳送。這種情形在圖6中示出。
圖6示出了位流包括10個Huffman代碼字的示例。在一個代碼字總是由一個頻譜值形成的情況下，這裡就可以對10個頻譜值進行編碼。然而，通常總是2個或4個頻譜值用一個代碼字共同編碼，這就是圖6示出包括20或40個頻譜值的一部分編碼位流的原因。在每個Huffman代碼字包括2個頻譜值的情況下，數字1標定的代碼字表示前2個頻譜值，第一個代碼字的長度比較短，這意味著前兩個頻譜值的值，即兩個最小的頻率係數，出現的比較頻繁。而帶有數字2的代碼字卻有較長的長度，這意味著已編碼的音頻信號中第3和第4個頻譜係數的量值較少，這就是它們被用一個較多的位來編碼的原因。還有，從圖6中可以清晰地看出，具有數字3、4和5的代碼字也出現得較頻繁，因為各代碼字的長度較小，數字3、4和5表示頻譜係數5與6或7與8或9與10。同樣的分析合適於帶有數字6至10的代碼字。
正如已經提到的，從圖6中顯然可以清晰地看出，在考慮用已知的編碼設備生成位流的情況下，用於對頻譜值編碼的Huffman代碼字以與頻率相關的線性增長方式被安排在位流中。
在信道出現故障的情況下，Huffman代碼的一個主要的缺陷是差錯的擴散。例如，可以假定圖6中的第二個代碼字受到幹擾。存在某一個不低的概率，即該差錯的第二個代碼字的長度也會被改變。因此它就不同於正確的長度。如果，在圖6的例子中，第二個代碼字的長度由於一個幹擾而被改變，對於一個編碼器而言就不再可能確定代碼字3至10的起點，即所表示的幾乎整個音頻信號的起點。這就意味著跟隨在已被幹擾的代碼字後面的所有其他代碼字就不能再被正確編碼，因為不知道這些代碼字從哪裡開始，並且因為由於該差錯而選擇了一個不正確的起點。
作為對該差錯擴散問題的一個解決方法，歐洲專利0612156號建議將可變長度的代碼字的一部分安排在一個柵格(raster)中，並把餘下的代碼字分散於餘下的空隙中，以便安排在一個柵格點(raster point)的一個代碼字的起點能在不進行全面解碼的情況下或者在不正確傳輸的情況下更容易找到。
確實，該已知的方法通過重新安排代碼字的方式對差錯的擴散提供了一些補救。對於某些代碼字而言，在位流中確定一個固定位置，餘下的空隙供餘下的代碼字使用。這並不耗費任何附加的位，卻能防止在出現差錯的情況下差錯在重新安排的代碼字之間擴散。
然而，該已知方法的效率上的一個決定性的參數取決於在實際應用中確定柵格的方式，即必須使用多少個柵格點，以及該柵格所必須具有的間隔等除了使用一個柵格來抑制差錯擴散的一般性建議之外，歐洲專利0612156號並未給出有關如何有效地設計該柵格以便一方面能夠進行耐差錯的編碼另一方面又能夠高效編碼的任何更為詳細的信息。
在本申請提交日之後發布的德國1947119.631號專利申請建議，不是把任何代碼字都定位於柵格點上，而是把那些從心裡聽覺(psycho-acoustic)的角度來看具有特殊意義的代碼字，即那些能夠對音頻信號起重要作用頻率值的代碼字定位於柵格點上。在圖5中示出了由這樣的一個編碼器生成的一個具有可變長度代碼字的數據流。和圖6中一樣，該數據流也包括10個代碼字，畫影線的為具有優先權的代碼字。第一優先權代碼字被定位於在第一柵格點100開始，第二個優先權代碼字被定位於在第二個柵格點101開始，第三個優先權代碼字被定位於在第三個柵格點102開始，第四個優先權代碼字被定位於在第四個柵格點103開始而第五個優先權代碼字被定位於在第五個柵格點104開始。第一節(segment)105由柵格點100和101定義。以同樣的方式，對第二節106，第三節107，第四節108以及最後一節109進行定義。圖5中示出，前兩節105和106的長度與107和108兩節的長度不同，而且還與最後一節109的長度不同。可以說，無優先權的代碼字6，7，8，9與10則在優先權代碼字之後被插入該數據流中，以使數據流被填滿。如圖5中所示，在該後公布的方法中，無優先權的代碼字接在被寫入的優先權代了之後被連續插入該柵格中。具體地講，無優先權的第6個代碼字跟在無優先權代碼字1的後面被寫入。105節中剩下的空隔被後隨的無優先權代碼字7填入，而無優先權代碼字7的剩餘部分即7b，則緊隨在優先權代碼字3的後面被寫入下一空隔即107節中。無優先權代碼字8至10執行同樣的過程。
在圖5中示出的該後公布的方法的優點是優先權代碼字1至5受到保護而免於差錯擴散的影響，因為它們的起點與柵格點重合併因此而被知曉。
例如，如果優先權代碼字2在傳輸中受到破壞，則在圖6中所示的現有技術中很可能解碼器將不能對餘下的任何代碼字3至10正確地進行解碼。然而在圖5所示的方法中，下一個代碼字，即優先權代碼字3，在柵格點102開始，這樣，該解碼器總會找到代碼字3的正確起點。因此，在圖5所示的方法中，不會有什麼系列差錯出現，而只是優先權代碼字2將被破壞。因此，該方法對定位於柵格點的優先權代碼提供了有效的保護。
然而，對於無優先權代碼字沒有有效的保護。參見圖5，破壞無優先權代碼字6，以至解碼器把短了一位的一個代碼字設想為不正確的代碼字6，這將導致不再能夠正確地對代碼字7進行解碼，因為正確的代碼字6的最後一位被解釋為下一個代碼字7的開始。因此，代碼字6中的一個差錯將導致由於序列差錯而非常可能不再能夠對跟隨在它後面的任何代碼字進行正確解碼，即使它們並未受到傳輸差錯的影響。
本發明的目的是找出一種寫入與讀出可變長度代碼字數據流的基本原理，以提供防止由於不理想的數據流傳輸而引起的序列差錯的具體保護方法。
通過根據權利要求1的生成一個數據流的方法，及通過根據權利要求15的讀出一個數據流的方法，並通過根據權利要求20的生成一個數據流的設備以及根據權利要求21的讀出一個數據流的設備，該目的得以實現。
本發明的是基於認識到具有可變長度代碼字的一個數據流必須如此配置使得於該數據流中的連續的代碼字必須被儘快分開以使解碼器不會由於一個傳輸差錯而生成數量非常大的序列差錯。為此，將被傳輸的可變長度的代碼字被分成多個集(set)。第一個集可以包括優先權代碼字，而第二個集可以包括無優先權代碼字。為了也對無優先權代碼字提供保護使之免受傳輸差錯的破壞，它們不能像在現有技術中那樣被簡單地寫入未被佔用的柵格，而是要被分散於各分立的節中。在對接收器進行已知的固定的分配之後，無優先權代碼字被如此地分配到各節，以致每個無優先權代碼字即來自第二個集的每個代碼字被分配到該數據流的一個不同的節。為使這一做法奏效，每個集只能具有與供該數據流使用的節的數量相同的代碼字。因此，第一集的代碼字被寫入柵格，使第一集的每個代碼字從一個柵格點開始。然後進行嘗試，把第二個集的每個代碼字如此地寫入數據流，使第二個集的每個代碼字被分配到一個不同的節。由於這種分配，即第二個集的每個代碼字被寫入一個不同的節，解碼器將不再僅連續地對第二個集的代碼字進行解碼，而是轉至在該柵格中為第二個集的每個代碼字設置的相應的節以便從該節中提取第二個集的相應的代碼字。
如果，第一個集的代碼字已被寫入一個節之後，該節已滿到只有部分空間可供分配給該節的第二集的代碼字使用或者根本就沒有空間了，則仍有空間的第二集的代碼字的那部分被寫入所分配的該節，餘下部分被儲存起來。如果對該代碼字已完全沒有空間，則該代碼字被整個地儲存起來，直至第二集的每個代碼字的分配已被嘗試。只有當此時才進行第二次嘗試，把第二個集的被儲存的部分的或被儲存的完整的代碼字按照預定的規則寫入仍未被佔用的節的部分中。
在柵格的配置使第一個集的代碼字中有比該節的長度要長的代碼字的情況下，可以儘早地採用相同的方法來寫入第一個集的代碼字。
一旦一個解碼器從數據流中提取了從柵格點開始的第一個集的代碼字，它將繼續提取第二個集的代碼字。在解碼器只找到第二集代碼字的一部分的代碼字的情況下，該部分將被存儲起來而該處理則繼續在一個不同的節中尋找第二集的下一個代碼字。僅在所有的節均在這種第一次嘗試中被搜索之後，第二個集的一個代碼字的缺失部分將在第二次或以後嘗試中被確定，或者其所分配的節已被第一集的代碼字佔用的第二集的一個代碼字被確定。
參見圖5，代碼字6中的一個差錯將因此而不再會導致代碼字7中的一個差錯，因為代碼字7會在一個與節105不同的節中開始，而且代碼字6的後面將是一個完全不同的不與其相鄰的代碼字。
為了進一步地說明，可以使用一個簡單的例子。該例子是基於假設存在第一集的兩個代碼字和第二集的兩個代碼字，也就是說總共四個可變長度的代碼字。為了與現有技術比較，進一步假定代碼字1與3加在一起的長度足以填入第一個節，而代碼字2與4加在一起的長度，足夠完全填入第二個節。在這種情況下，根據現有技術的一個設備與根據本發明的一個設備一樣對相同的數據進行寫操作。根據現有技術的設備首先會把優先權代碼字1與2寫入兩個柵格點，然後在代碼字1的後面寫入代碼字3並把代碼字4寫入柵格中未被佔用的下一個空隔，也就是說寫在代碼字2的後面。純粹是巧合，代碼字4因此而不再(至少是部分地)位於第一節中，而是完全位於第二節中。
根據本發明的一個設備一開始將把第一集的代碼字寫至相應的柵格點並且然後將把第二集的第一個代碼字寫入第一節中並把第二集的第二個代碼字寫入第二節中，而無論在第一節中是否仍有空間。根據該發明的該設備無論如何都要因此而嘗試把第二集的每個代碼字寫入不同的節中。
即使由於巧合兩個數據流看起來相同，對於將從該數據流中提取可變長度代碼字以便根據解碼器要求的順序安放它們的接收器而言仍將出現明顯的差別。在現有技術中，一個用於提取的設備一開始將讀出第一個柵格點的代碼字1和第二個柵格點的代碼字2，以便獲得第一集的代碼字。然後，根據現有技術的一個設備將轉至餘下的數據流的開端並在那裡讀取代碼字3，並接著讀取代碼字4。
根據本發明的一個設備，在讀取第一集的代碼字1與2之後，也將轉至餘下的數據流的開始端並在那裡讀取代碼字3。然而，根據該發明的設備將在此後跳至下一節以便讀取第四個代碼字的開始端，即第二集的第二個代碼字。
下面，將假設第三個代碼字，即在假定的數據流中將被寫在第一集的第一個代碼字後面的第二集的第一個代碼字，已經受到幹擾，以致解碼器將把這同一個代碼字理解為比其實際長度要短的一個代碼字。在這種情況下用於讀取數據流的該已知設備將讀取第三個代碼字並將由於該傳輸差錯而非常快地停止並判定實際上屬於第三個代碼字的餘下的一位或多位是第四個代碼字的開始端。然而，根據本發明的設備將跳至在第三個代碼字被終止後的下一節，並將因此而正確地確定第四個代碼字的開端。
通過使用這一簡單的例子，從中可以清楚地看出本發明的最重要的優點，即由於把第二集的代碼字分到獨立的節，而在第二集的代碼字，比如說也可以是無優先權代碼字中防止序列差錯。然而，在現有技術中，正如參照圖5所描述的，即使由現有技術以及由本發明生成的可變長度代碼字的數據流由於巧合而可能是相同的，序列差錯也會出現。
下面將參照附圖對本發明的優選實施例進行詳細解釋，其中
圖1示出了所發明的用於生成一個可變長度代碼字數據流的設備；圖2示出了所發明的用於讀取具有可變長度代碼字的數據流的設備；圖3通過可變長度代碼字的三個集示出了所發明的方法的一個程序圖；圖4示出了用於說明所發明的讀取根據圖3生成的一個數據流的方法的一個程序圖；圖5示出了由一個已知設備生成的並且其中的優先權代碼字受到差錯擴散影響的一個數據流；圖6示出了已在其中按照優先權代碼字與無優先權代碼字進行分類的一個數據流。
在對圖1進行更為詳細的描述之前，應該注意，在技術上對於可變長度代碼字的編碼也稱作平均信息量編碼。平均信息量編碼的一個典型例子是所謂的Huffman編碼。原則上，在Huffman編碼中，對被編碼的信息符號進行統計分析以便確定用於比不大頻繁出現的信息符號更頻繁出現的信號符號的較短的代碼字。在一個完整的Huffman代碼中，所有的代碼字均終止於一棵代碼樹的端點或分枝。例如，一個Huffman解碼器連續地讀入一個具有Huffman代碼字的數據流，並通過圖解的方法，跳至具有它額外讀入的每一位的該指定的代碼樹的一個分枝，在經過一定數量的跳轉，即與該代碼字的位數亦即該代碼字的長度相對應的數量的跳轉之後，它到達不再具有進一步分枝的、並因此而是一個代碼字的一個枝端。該解碼器於是獲知一個新的代碼字從下一位開始。每有要求，該處理即重複一次，直至該數據流被完全讀入為止。每次當Huffman編碼器跳回起始點，即該樹的根部時，一個代碼字即在其始點出現。由於代碼字的長度是由代碼字自身或由編碼器及解碼器中已知的代碼樹默定的，可以看出，數據流中導致一個位錯位的一個幹擾會在代碼樹中對解碼器產生誤導，可以說這將使解碼器結束於一個不同的代碼字，即可能具有與正確的代碼字不同長度的一個錯誤的代碼字。在這種情況下，一旦到達錯誤的代碼字，解碼器將向回跳轉，而且由於後隨的位，再次從代碼樹中的一個分枝點向另一個分枝點運動。然而，對於該解碼器而言，避免序列差錯是不可能的，除非其巧合地結束於「正確的跟蹤目標」。
因此，差錯防護，比如由本發明提供的差錯防護，必須進行，以保證耐差錯的傳輸。因此，可以說，根據本發明的用於生成一個可變長度代碼字數據流的設備可以作為Huffman編碼器的發送或輸出級，而用於讀取可變長度代碼字數據流的設備則可以作為Huffman編碼器的接收或輸入級。由此可以看出，本發明不僅適用於Huffman編碼器，而且也適用於易於出現序列差錯的具有可變長度代碼字的任何代碼。
圖1示出了一個所發明的用於生成一個可變長度代碼字數據流的設備10，該設備具有一個輸入埠和一個輸出端14。在輸入端12，可變長度代碼字生成，而在輸出端14，耐差錯的數據流被輸出。最好設備10的輸入端12處的可變長度代碼字事先已進行了預分類，使得優先權代碼字處於第一集，較不重要的代碼字處於第二集而更不重要的代碼字處於第三集，等等。
該可變長度代碼字被輸入到用於把第一集的代碼字寫入數據流的一個設備16中，這就使第一集的代碼字各自從柵格點開始。
此外，該可變長度代碼字被輸入到用於把第二集的代碼字寫入數據流的一個設備18中，並為第二集的每個代碼字分配一個不同的節。因此，在兩個設備16與18之間的數據流中，只有第一集的所有代碼字被送至柵格點。在可變長度代碼字僅由兩個集的代碼字組成的情況下，則耐差錯的數據流已經出現在設備18的輸出端。在存在多於兩個集的可變長度代碼字的情況下，還有用於把相應集的代碼字寫入數據流的其他設備，用標號20以符號形式示出。
圖2示出了所發明的用於讀取在輸出端14(圖1)輸出的耐差錯數據流的一個設備22，其具有一個輸入端24和一個輸出端26。在輸入端24輸入耐差錯的數據流，以便在輸出端26輸出其順序與在輸入端12(圖1)形成的順序相對應的可變長度代碼字。用於讀取數據流的設備22包括用於通過跳至柵格點的方式提取第一集的代碼字的一個設備28，用於通過跳至餘下的數據流的柵格點的方式提取第二集的代碼字的一個下遊設備30以及，如果必要，用於提取和其他的集一致的代碼字的其他設備32，如果存在這樣的集的話。
在以圖3為基礎，通過一個例子對由設備10(圖1)實現的方法進行詳細解釋之前，首先將給出該方法的概要。可用的代碼字被分成多個集。除了最後一個之外，每個集包括與所存在的可用的節一樣多的代碼字。在最佳的情況下，一個集含有與所存在的可用的節一樣多的代碼字。然而，一個集也可以含有更多或者更少的代碼字，正如對於最後一個集而言幾乎必將是這種情況，因為可變長度代碼字的預定數量必須假定。如果存在M個節而且如果一個集有N個代碼字，則被寫至柵格點的代碼字的數量與M和N中的最小者一致，而在根據該發明的柵格中存放該N個代碼字的嘗試的次數則與M和N中的最大者一致。
最好是，第一集有最重要的代碼字，即表示與其他的信息符號相比更為重要的信息符號的優先權代碼字。接下來的集中含有按照由一個預選算法提供的順序排列的較不重要的代碼字，最好是該算法還對優先權代碼字和無優先權代碼字進行分類。這些集由設備10連續地寫入。寫入一個集需要幾次嘗試。在第一次嘗試中，當前集的第一個代碼字被寫入第一節，以此類推，直至當前集的最後一個代碼字被寫入最後一個節為止。當然，一個代碼字可以按照某一確定的規則從第二個，從第三個或從任何其他的節開始繼而寫入每個節中。
如果一個代碼字不能填入一個節，該代碼字的餘下部分則被儲存起來。在第二次嘗試中，第一個代碼字的餘下部分，如果存在的話，則被優先寫入第二個節，以此類推，直至最後一個代碼字的餘下部分被優先地寫入第一個節。這樣的一種算法還被稱為模數位移(moduloshift)。顯然，在下一輪，即下一次嘗試中，有關一個代碼字的餘下部分是寫入後隨的第一個節還是後隨的第三個節的預定規則是可以任選的。
一旦一個集被全部寫入，就開始寫下一個集。為了防止擴散差錯，還要根據該發明的一個優選實施例，改變在一個節內的集與集之間的寫操作方向。例如，第一集的代碼字從左向右寫，而第二集的代碼字從右向左寫，等等。因此，通過本發明，也可以說，根據該優選的實施例，一個柵格點的第二側端被用於絕對的差錯防護。
上面簡要概述的系統應用能夠非常有力地降低對一個特定代碼字的差錯擴散概率的值。隨著集被連續寫入以及隨著一個集的每個代碼字被賦分配到一個特定的節並被寫入該節，如果在該節中仍有空間，那麼沒有差錯從一個集中的一個代碼字向該集中的下一個代碼字擴散就是可能的，因為一個解碼器在解碼時總是從一個節跳至一個節而且並不認為一個代碼字的開端位於前一個代碼字結束的地方，在現有技術中的事實就是如此。如果由於可用的空間不足以完整送入一個代碼字該代碼字只是部分地被寫入該節中，則至少差錯擴散的可能性降低了。
根據本發明的一個優選實施例，節寬的選擇使優先權代碼字完全填入這些節。因此，寫第一集只需要一次嘗試。然而，這是任意的。通常，由於目的在於大量的柵格點用於一個數據流，即一個節長要儘可能的小，第一集的代碼字要長於該節長的情況也可以出現。然而，這種情況會像寫第二個集一樣對待，即，也按照一個必須為編碼器以及為解碼器所知的預定規則。
圖3通過一個例子解釋了所發明的用於寫入可變長度代碼字的方法。在該例中，有15個可變長度代碼字30，被事先分成具有6個代碼字1至6的第一集，也有6個代碼字7至12的第二集以及具有餘下的3個代碼字13至15的第三集。如圖3中所示，代碼字30具有可變長度。
根據本發明的一個優選實施例，節長，即該節的長度，要長於第一集的最長的代碼字的長度。第一集的代碼字被安置於柵格點41至46，其中，對於最後的一個節6，一個未被使用的柵格點由一條點劃線指明，然而，由於該數據流的端點47可以說也能被認為是一個柵格點，於是由一條點劃線指明的該柵格點就是多餘的了。第一節6因此而長於其他節，然而這與本發明完全無關。一般來講，節可以有在數據流內變化的任意長度，因為可以理解，一個節的當前長度必須為解碼器所知，以便該發明的優點能夠得到利用。
首先，第一集的代碼字在步驟a)中被寫入數據流，這將形成由31標明的不連貫的數據流，其中第一集的代碼字如在整個圖3中表示寫操作的方向的箭頭48所指明的那樣，從左向右被寫入各自相應的節中。由於選擇的節長長於第一集的代碼字的最大長度，在步驟a)中只要一次嘗試。如果節較短，則相應地要求較多的嘗試。
現在在步驟b)中把第二集的代碼字寫入數據流31。為了實現高耐差錯，第二集的代碼字最好不要像第一集的代碼字那樣從左向右寫，而是如由寫方向的相應箭頭指明的那樣，相應地從第二個柵格點，例如第一個節的柵格點42開始從右向左寫。第二集的代碼字的寫入要按照一個預定的分配法則進行，比如說在選定的例子中，第二集的第一個代碼字將被寫入第一集的第一個代碼字的同一個節中，然而，總是要以在該節中仍有空間為條件。從第一次嘗試中形成的數據流32表明，在第一個節中只有供寫入代碼字7的起始段的空間。
和把代碼字第7的第二部分寫入第二節的現有技術相比，代碼字第7的第二部分，即7b)被儲存起來以供在第二次嘗試中按照一個預定規則，即按照一個也必須為解碼器所知的規則將其寫入數據流。圖3清晰地顯示出，在第二節中，在代碼字第2與第8之間仍有足夠的空間供代碼字第7的最後部分進入。如果沒有足夠的空間，該代碼字的第三部分將被送入第三節。這樣，在圖3中，用於把代碼字第7送入數據流的預定規則就在於在所有的情況下均由一個節進行處理。當然，也可以由兩個節或者三個或更多的節進行，這樣作的結果，就能使第二個節7b)在下一次嘗試中被寫入第三個節，被寫入第五個節，等等，而不是第二個節。被用於在某個地方接收段7的第二部分的節的順序是任意的。然而，該順序對解碼器必須是透明的，以便被重新分類的數據流能被重新讀取。
現在，第三集的代碼字13至15被送入所形成的仍然不連貫的數據流33。從步驟b)類推，這最好按照同一分配規則執行，使第三集的第一個代碼字被分配到第一節，第三集的第二個代碼字被分配到第二節，第三集的第三個代碼字被分配給第三節，等等。對於第三集而言該分配規則完全是任意的並且也可以與用於第二集的分配規則不同，即根據該發明，一個集的每個代碼字被分配給一個不同的節。
步驟c)中的第一次嘗試僅在把代碼字第15的第一段送入，形成一個不連貫的數據流34這一點上是成功的。代碼字13，14與代碼字15的第二段即15b)被儲存起來以供在第二、第三、第四、第五以及第六次嘗試中被接納，其中第二段15b)會在第二次嘗試中被接納於第四節(數據流35)，其中在第三次嘗試中沒有任何東西被接納，其中代碼字14的開始段會在第四次嘗試中被接納(數據流36)，其中代碼字14的最後一段即14b會在第五次嘗試中被接納(數據流37)而其中，最後，第三集的第一個代碼字會在第六次並且是最後一次的嘗試中被送入第六節，為在此圖示的例子形成耐差錯的數據流38。利用圖3描述的方法保證該耐差錯數據流的長度完全相等於這些可變長度代碼字的長度之和，對於用於數據縮減的平均信息量編碼而言這是不言而喻的。然而，本發明並不局限於具有最小長度的耐差錯數據流，因為耐差錯是不受可能出現的任何填充位的影響的。
對於圖3中所示的增強型數據流，可以看出代碼字8的起點即柵格點43完全獨立於代碼字7的終點。還有，代碼字9的起點即柵格點44完全獨立於代碼字第8的終點。另外，應該注意到，由於寫順序相反，第一節中代碼字第1中的一個數據差錯，比如說將由於該數據差錯而導致不正確的代碼字比正確的代碼字第1短一位的數據差錯，不會導致代碼字7a的起始段的破壞，因為後者是從右向左而不是從左向右寫的。如果它從左向右寫，解碼器會把從一開始的正確代碼字第1餘下的一位看作是代碼字第7的起始位，這將導致從1至7的序列差錯。然而，該序列差錯不會擴散至8，因為由於代碼字8所選的寫順序是從右向左因而它還是完全獨立於代碼字7的。如果代碼字第8的寫順序與第一集的代碼字的寫順序相同，差錯就不會從7向8擴散並且，因為代碼字8會由於分配規則而挨著代碼字2寫在第二部分7b的前面，並且因此而不受不正確段7b的影響。
通過一個恰當的例子，圖4示出了用於讀取耐差錯數據流38的設備的運行狀況。一開始，在步驟a)從耐差錯的數據流提取第一集的代碼字。為此，可以與Huffman解碼器配對使用的所發明的該設備從第一個柵格點41開始讀取第一集的代碼字，從第二個柵格點42開始讀取第一集的代碼字第2，等等，直至第一集的所有代碼字1至6被讀入為止。用於讀取數據流的設備選擇與用於生成數據流的設備所使用的方向相同的方向，這是不言而喻的。
接著，在步驟b)從餘下的數據流50提取第二集的代碼字。這裡，解碼器跳至第一節的第二個柵格點42獲取第二集的代碼字7的起始段，隨後，它並不讀入第二段7b，而是首先儲存7a，以便接著從第二節的第二個柵格點開始讀入第二集的第二個代碼字，等等。其結果是一個殘餘的數據流51，其中的第一節已被完全騰空。由於該解碼器現在並不連續讀取代碼字7，而總是根據用於生成該數據流的設備的分配規則逐節地讀取，則已被描述的能夠有力地降低序列差錯擴散的耐差錯就得到了保證。
在提取第二集代碼字的第二次嘗試中，代碼字7b的第二部分根據現有的寫方向被讀入第二節中，於是，僅有第三集的代碼字餘留於由此產生的數據流52中。(第二節現在是空的。)這些代碼字是在步驟c)中提取的，其中代碼字15的起始段一開始已在第一次嘗試中被確定，然而並不必儲存，因為在第三節中未曾發現代碼字15是完整的。第三節現在也是空的，然而，柵格點仍然存在，以便解碼器能夠用它們為自己定向。在第二次嘗試中，能夠發現代碼字15是完整的。然而，通過數據流54可以看出，在節3中對代碼字14以及在節14中對代碼字15的搜索仍未成功。儘管如此，在第四次嘗試中，在第5節中對代碼字14的搜索產生肯定的結果。然而，代碼字14是不完整的，這就是起始段14a被儲存以便在第五次嘗試中對餘下的數據55進行檢查，並且在最後的第六次嘗試中全部地讀入數據流56的原因，現在數據56僅由第六節並和代碼字13組成。
雖然在前面的例子中，通過舉例，僅對把代碼字分成起始段與結束段的一個方法進行了說明，但是原則上講，任何類型的方法均是可行的。只要解碼器遵循把第二集的或者第三級的以及其他集的代碼字分別地分配給不同的節，耐差錯的編碼就會得到保證。而且，進入數據流的代碼字的結束段的分類是任意的，只要解碼器或者解碼器的上遊讀入電路確知在編碼器中執行了哪一個預定規則。
權利要求
1.用於生成可變長度代碼字數據流的方法，其中該數據流被分成多個代碼字集，一個具有用於該數據流的多個柵格點的柵格，兩個相鄰的柵格點(41，42)定義一個節(40)，並且該柵格含有多個節，該方法包括以下步驟a1)寫入第一集的代碼字(1-6)使代碼字的起點位於不同節的柵格點上；a2)如果一個代碼字比一個節要長，依照第一個預定規則，把該代碼字的餘下部分寫入該柵格的在步a1)之後未在上面寫信息的一個區，直至第一集的所有代碼字均被寫入該柵格為止；b1)、如果相應的代碼字適合於該節，把第二集的每個代碼字寫入依照一個預定的分配規則分配給各個代碼字的一個節，其中第二集的每個代碼字被分配給一個不同的節；b2)如果僅有相應的代碼字(7)的一部分適合於所分配的節，或者如果所分配的節是滿的，把第二集的相應的代碼字(7)的部分(7a)寫入所分配的節(1)並把代碼字(7b)的餘下部分或者分配給該滿節的完整的代碼字(13)儲存起來；b3)依照第二個預定規則，把在步驟b1)、b2)中不適合於各自的節的所儲存的餘下部分(7b)或者所儲存的完整的代碼字(13)寫入在步驟b1)與b1)之後未在上面寫入信息的柵格的一個區，直至第二集的所有的代碼字被寫入該柵格為止。
2.如權利要求1中所要求的方法，在該方法中，第一集的代碼字按照一個順序出現，其中這些代碼字被按照它們的順序寫入相鄰的節中。
3.如權利要求1或2中所要求的方法，在該方法中，在步驟a2)中的第一個預定的規則如下i)把第一集的一個代碼字的餘下部分的至少一部分寫入跟隨在其中出現該代碼字的起始段的節的後面的節中，如果在該節中存在供該餘下部分的至少一部分使用的空間的話，並且ii)如果這樣的代碼字出現的話，對第一集的所有其他代碼字的餘下部分執行步驟(i)；並且iii)執行步驟(i)、(ii)，其中對於每個餘下部分一個餘下部分用一個節執行，直至第一集的所有代碼字均被寫入該數據流(31)為止。
4.如由前面的任何一個權利要求所要求的方法，在該方法中，第二集的代碼字按照一個順序出現，並且預定的分配規則把第二集的第一個代碼字分配給第一集的第一個代碼字的起點所在的節，把第二集的第二個代碼字分配給第一集的第二個代碼字的起點所在的節並且，如果存在的話，把第一集的每個其他的代碼字分配給其第一集的相對應的代碼字起點所在的節。
5.如由前面的任何一個權利要求所要求的方法，其中的第二個預定規則等同於第一個預定規則。
6.如由前面的任何一個權利要求所要求的方法，其中，依照第一或第二個預定規則，如果在緊隨於所分配的仍然留有餘下部分的節的後面的各節中僅有這麼多空間的話，不能完全裝入所分配給的節的相應的集的一個代碼字要分成三個或三個以上的部分。
7.如由前面的任何一個權利要求所要求的方法，其中的柵格點被等間隔分開，以此獲得除最後一個節之外的等長節，其中的等長節要長於或等長於第一個集的最長的代碼字，以使第一集的每個代碼字適合於相應的節。
8.如由前面的任何一個權利要求所要求的方法，其中第一集的代碼字以第一寫方向分別從各節的第一個柵格點開始寫入，而其中第二集的代碼字以與第一寫方向相反的第二寫方向分別從各節的第二個柵格點開始寫入。
9.如在權利要求8中所要求的方法，其中存在代碼字的第三集，其中在第二集的所有代碼字寫入該柵格後，第三集的代碼字再以第一寫入方向寫入該柵格。
10.如由前面的任何一個權利要求所要求的方法，其中的代碼字是Huffman(霍夫曼)代碼字。
11.如由前面的任何一個權利要求所要求的方法，其中的代碼字代表信息符號，而其中第一集的代碼字代表比第二集的或者此外的其他集的代碼字更重要的信息符號。
12.如在權利要求11中所要求的方法，其中的信息符號是一個音頻信號的頻譜值，而第一集的代碼字是從心理聽覺的觀點來看更為重要的頻譜值，其受到保護以免於由於數據流中的一個傳輸差錯而引起的任何差錯的擴散。
13.如由前面的一個權利要求所要求的方法，其中所形成的數據流的長度等於可變長度代碼字的長度之和。
14.如由前面的任何一個權利要求所要求的方法，其中存在兩個以上的代碼字集，該方法還包括以下步驟對代碼字的其他更多的集的代碼字執行步驟b1)、b2)和b3)，其中的第二個預定規則與步驟b2)的第二個預定規則對應，並且其中該預定分配規則與步驟b1)的預定分配規則相對應。
15.用於讀取一個可變長度代碼字數據流的方法，其中的數據流包括多個代碼字集的代碼字，其中一個柵格被指定用於該數據流(38)，該柵格包括柵格點(41，42)其中兩個相鄰的柵格點(41，42)定義一個節(40)，其中該數據流包括至少兩個節，該方法包括以下步驟a)通過以下各步驟從數據流(38)提取第一集的代碼字a1)對於每個節，跳至一個柵格點並讀取在那裡開始的一個代碼字；a2)如果從一個柵格點開始的該代碼字在該節的終點並未結束，把該代碼字的已讀取的段儲存起來，並且a3)根據在形成該數據流時使用的第一個預定規則確定該代碼字的餘下部分；b)通過以下各步驟從在步驟(a)之後留下的數據流(50)中提取第二個代碼字集的代碼字b1)對於每個餘下的節，根據在形成該數據流時使用一個預定的分配規則跳至該節的一個柵格點，並讀取在那裡開始的代碼字，以便獲得第二集的代碼字；b2)如果第二集的一個代碼字在一個相應的節的終點並未結束，把讀取的第二集的該代碼字的段儲存起來；b3)根據在形成該數據流時使用的第二個預定規則，確定該代碼字的餘下部分或者在一個柵格點未出現的代碼字。
16.如在權利要求15中所要求的方法，其中的數據流包括多個兩個集的代碼字，該方法還包括以下步驟通過重複步驟b1)、b2)和b3)來提取第三集的代碼字，其中第二預定規則等同於步驟b3)的第二預定規則，並且其中的分配規則等同於步驟1)的分配規則。
17.如在權利要求15或16中所要求的方法，其中在形成數據流時所使用的分配規則把第二集的第一個代碼字分配給在其中第一集的第一個代碼字開始的一個節，其中，在步驟b1)，解碼器跳至第一個柵格點(41)以獲取第二集的第一個代碼字，解碼器跳至第二個柵格點(42)以獲取第二集的第二個代碼字，以此類推，其中，如果沒有或者只有第二集的一個代碼字的一部分在第一柵格點(41)開始，在根據第二預定規則確定一個丟失了的代碼字或者一個代碼字的一個丟失了的部分之前，解碼器一開始從所有的柵格點開始讀取。
18.如由權利要求15至17中的一個權利要求所要求的方法，其中步驟a3)中的第一個預定規則如下對於一個讀取的代碼字的每個存儲段，跳至在步驟a1)之後餘留的數據流中的下一個柵格點，以確定該代碼字的餘下部分；如果一個代碼字能被讀至終點，把已被讀至終點的該代碼字與所儲存的段連接起來，以完整地獲得第一集的代碼字，否則，則儲存已被讀取的一個段並重複跳至下一個柵格點的步驟，直至第一集所有的代碼字出現。
19.如由前面的任何一個權利要求所要求的方法，其中在第一個代碼字集中存在的代碼字與在該數據流中存在的節一樣多，而且其中在其他的一個集或多個集中的代碼字的數量等於或小於第一集中的代碼字的數量，以使第一集中所有的代碼字均被寫至柵格點。
20.用於生成可變長度代碼字的數據流的設備(10)，該數據流被分成多個代碼字集，其中存在一個具有用於該數據流的多個柵格點的柵格，其中兩個相鄰的柵格點(41，42)定義一個節(40)，該柵格包括多個節，該設備包括a)用於寫入第一集的代碼字(1-6)以使各代碼字的起點在各不同節的柵格點的設備(16)，其中，設備16是這樣設置的，使得如果一個代碼字長於一個節，則依照第一個預定規則把該代碼字的餘下部分寫入該柵格的在步驟a1)之後未在上面寫信息的一個區，直至第一集的所有代碼字均被寫入該柵格為止。b)用於把第二集的每個代碼字寫入按照一個預定的分配規則被分配每個單個代碼字的一個節中的裝置(18)，其中如果相應的代碼字適合於該節的話，第二集的每個代碼字被分配給一個不同的節，其中裝置(18)是這樣配置的如果相應的代碼字只有一部分適合於所分配的節，或者如果所分配的節是滿的，則把第二集的該相應的代碼字(7)的該部分(7a)寫入所分配的節(1)並將該代碼字的餘下部分(7b)或者把分配給該滿節的整個代碼字(13)儲存起來；把在步驟b1)、b2)中不適合於相應的節的所存的餘下部分(7b)和所存的整個代碼字(13)按照第二預定規則寫入該柵格的在步驟b1)和b2)之後未在上面寫信息的一個區，直至第二集的所有代碼字均被寫入該柵格為止。
21.用於讀取一個可變長度代碼字數據流的設備(22)，其中該數據流包括多個代碼字集的代碼字，其中為該數據流(38)指定一個包括柵格點(41，42)的柵格，其中兩個相鄰的柵格點(41，42)定義一個節(40)，其中該數據流至少包括兩個節，該設備包括a)用於從數據流(38)提取第一集的代碼字的一個裝置(28)，該裝置被如此配置使之對於每個節，跳至一個柵格點並在那裡開始讀取一個代碼字；如果在一個柵格點開始的該代碼字未能在該節的終點結束，把該代碼字的所讀取的段儲存起來；根據在形成該數據流時使用的第一預定規則確定該代碼字的餘下部分；和b)用於從在步驟a)之後餘下的數據流(50)中提取第二代碼字集的代碼字的一個裝置(30)，該裝置被如此配置使之對於每個餘下的節，根據在形成該數據流時使用的一個預定的分配規則跳至該節的一個柵格點，並讀取在那裡開始的代碼字，以便獲得第二節的代碼字，如果第二集的一個代碼字未能在一個相應的節的終點結束，則把第二集的該代碼字的所讀取的段儲存起來；根據在形成該數據流時使用的第二預定規則確定該代碼字的餘下部分或未在一個柵格點出現的該代碼字。
全文摘要
本發明涉及從被分成多個代碼字集的可變長度代碼字生成數據流的方法,其中為該數據流確定一個包含多個節的柵格,其中兩個相鄰的柵格點(41,42)定義一個節(40)。第一集的代碼字(1－6)從這些柵格點開始被寫入該數據流。接著,第二集的代碼字依照一個預定的分配規則被寫入該數據流,其中第二集的每個代碼字被分配到一個不同的節。不能根據其分配被寫入的完整的代碼字或代碼字的部分被儲存起來並在後面的寫入嘗試中被送入該數據流,其中對按照預定規則進行的分配,每一次嘗試都是變化的。對於任何接下來會出現的集,該過程被類似地重複進行。這樣,第二集的代碼字的終點就與後接的第二集的代碼字的起點分開,因為一個集的相應的代碼字是逐節寫入的。這就減小了差錯擴散。
文檔編號H03M7/42GK1345484SQ00805534
公開日2002年4月17日 申請日期2000年1月17日 優先權日1999年2月23日
發明者拉爾夫·斯伯奇內德, 馬丁·迪爾茲, 皮埃爾·勞伯, 米歇爾·舒格 申請人:弗蘭霍菲爾運輸應用研究公司