text: 在編碼理論中，噴泉碼是一類抹除碼，這種編碼能夠從一組給定的源符號序列中產生一串不限長度的編碼符號序列，在理想情況下，從編碼符號序列中獲得大小和源符號相同或稍大的任意子集，便可恢復源符號。術語“噴泉”或“無位元速率”是指此類編碼不表現出固定的編位元速率。最優的噴泉碼應當能夠從任意"k"個編碼符號中恢復出"k"個源符號。噴泉碼被認為具有高效的編解碼演算法，能以高機率從任意"k’"個編碼符號恢復"k"個源符號。LT碼是第一種實際可用的噴泉碼。隨後提出的Raptor碼和線上碼加入了輸入符號的預編碼階段，從而實現了編解碼的線性時間複雜度。應用.噴泉碼可靈活適用於固定編位元速率或無法先驗確定出固定編位元速率的地方，及需要高效編解碼大量資料之處。一個示例是資料輪播，其上會連續廣播一些大檔案到一組接收器中。採用固定位元速率的抹除碼，丟失源符號另一種應用是在可靠多播中的混合ARQ：一個接收器請求的奇偶校驗資訊可能會對多播組中的“所有”接收器有用。標準中的噴泉碼.目前最高效的噴泉碼為Raptor碼，有著非常高效的線性時間編解碼演算法，編解碼時每生成一個符號只需要很少的常數次XOR運算。IETF RFC 5053 中詳細規定了系統Raptor碼，其已為IETF之外的多個標準所採用，如用於廣播檔案傳遞和流服務的3GPP MBMS標準、用於在DVB網路中提供IP服務的DVB-H IPDC標準和用於在IP網路中提供商用電視服務的DVB-IPTV標準。這種編碼支援最多8192個源符號的源區塊，每個源區塊能生成多達65536個編碼符號。當源區塊有1000個源符號時，該編碼的平均相對接收開銷為0.2%，而相對接收開銷小於2%的機率為99.9999%。相對接收開銷定義為在恢復原始源資料時，所需的超出源資料長度的編碼資料，表示為源資料大小的百分比。例如，如果相對接收開銷為0.2%，那麼這意味著，大小為1 MB的源資料可以從1.002 MB的編碼資料中恢復。更高階的Raptor碼靈活性更強，接收開銷更少，稱為RaptorQ，已被IETF接受。這種編碼支援最多56403個源符號的源區塊，每個源區塊能生成多達16777216個編碼符號。該編碼有很高的機率，能從任何一組等於源區塊中源符號數量的編碼符號中恢復源區塊，而在罕見情況下，只比源區塊中源符號數量稍多。資料儲存中的噴泉碼.抹除碼在資料儲存應用中有使用，因其在給定級別的冗餘和可靠性下，能節省大量的儲存單元。用於資料儲存的抹除碼，特別是在分散式儲存應用中，相比用於通訊或資料流時，其設計要求有很大不同。用於資料儲存系統中的編碼，要求之一是系統形式，即，原始訊息符號是編碼符號的一部分。系統形式使訊息關閉符號能直接讀取，而不必從儲存單元中解碼。此外，由於儲存節點之間的頻寬和通訊負載可能會成為瓶頸，允許最小通訊的編碼會非常有幫助，特別是當一個節點發生故障，且需要進行系統重建以恢復冗餘到初始水平時。在這方面，會希望故障發生時，噴泉碼能高效地執行修復過程：當丟失單個編碼符號時，要找回它，不應有太多關於其他編碼符號的通訊和計算。事實上，修復的延遲有時可能比節省儲存空間更重要。可修復噴泉碼預計將能完成噴泉碼在儲存系統的設計目標。關於噴泉碼的詳細調查及其應用，可以在此找到。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 噴泉碼
metadata.url: https://zh.wikipedia.org/wiki?curid=4522547