Торнадо кодтары: қателерді түзеу және деректерді қалпына келтіру әдісі

Кіріспе

Кодтау теориясында Торнадо кодтары – қателерді түзетуге қолдау көрсетілетін өшіру кодтарының класы. Торнадо кодтары, Reed–Solomon өшіру кодтарына қарағанда, тұрақты C санымен артық блоктарды қажет етеді, бірақ оларды жасау және өшірулерді түзету әлдеқайда жылдам. Торнадо кодтарының бағдарламалық қамтамасы арқылы іске асырылуы, кішкентай ұзындықта Reed–Solomon өшіру кодтарынан 100 есе, ал үлкен ұзындықта 10 000 есе жылдам. Торнадо кодтары енгізілгеннен бері, Online кодтары, LT кодтары және Raptor кодтары сияқты көптеген басқа да ұқсас өшіру кодтары пайда болды. Торнадо кодтары қабатты тәсілді қолданады. Соңғы қабаттан басқа барлық қабаттарда LDPC қателерді түзету коды қолданылады, ол жылдам, бірақ сәтсіздікке ұшырау мүмкіндігі бар. Ал соңғы қабатта Reed–Solomon түзету коды қолданылады, ол баяурақ, бірақ сәтсіздікті қалпына келтіру тұрғысынан ең оңтайлы. Торнадо кодтары деңгейлер санын, әр деңгейдегі қалпына келтіру блоктарының санын және соңғы емес қабаттар үшін блоктарды жасауға қолданылатын таралуды анықтайды.

Шолу

Кіріс деректері блоктарға бөлінеді. Блоктар – бірдей өлшемдегі биттер тізбегі. Қайтару деректері кіріс деректерімен бірдей блок өлшемін пайдаланады. Блоктың (кіріс немесе қалпына келтіру) жоғалуы басқа тәсілмен анықталады. (Мысалы, дискідегі блок CRC тексеруінен өтпейді немесе белгілі бір реттік нөмірі бар желілік пакет келмейді.) Қайта қалпына келтіру блоктарының санын пайдаланушы анықтайды. Содан кейін деңгейлер саны және әр деңгейдегі блоктар саны анықталады. Әр деңгейдегі сан бірден кіші B коэффициентімен есептеледі. Егер N кіріс блогы болса, бірінші қалпына келтіру деңгейінде B*N блогы, екіншісінде B*B*N, үшіншісінде B*B*B*N және т.б. болады. Соңғы деңгейден басқа барлық қалпына келтіру деңгейлері xor (ексклюзивті немесе) операциясын қолданатын LDPC кодын пайдаланады. XOR екілік мәндермен – 1 және 0-мен жұмыс істейді. Егер A және B әртүрлі мәндерге ие болса, A xor B = 1, ал егер A және B бірдей мәндерге ие болса, 0 болады. Егер сізге (A xor B) және A нәтижесі берілсе, B мәнін анықтауға болады. (A xor B xor A = B). Сол сияқты, егер сізге (A xor B) және B нәтижесі берілсе, A мәнін анықтауға болады. Бұл бірнеше мәндерге дейін жалғасады, сондықтан (A xor B xor C xor D) нәтижесі және кез келген 3 мән берілсе, жоғалған мәнді қалпына келтіруге болады. Бірінші деңгейдегі қалпына келтіру блоктары – кіріс блоктарының xor жиыны. Сол сияқты, екінші деңгейдегі қалпына келтіру блоктары әрқайсысы бірінші деңгейдегі блоктардың xor жиынынан құралады. Xor операциясына қолданылатын блоктар қайталанусыз кездейсоқ түрде таңдалады. Дегенмен, қалпына келтіру блогын жасау үшін таңдалған блоктардың саны әр деңгей үшін нақты үлестірімге сәйкес келеді. Xor операциясы жылдам болғандықтан және қалпына келтіру блоктары кірістегі (немесе төменгі қалпына келтіру деңгейіндегі) блоктардың тек бір бөлігінің xor-ы болғандықтан, қалпына келтіру блоктарын жылдам жасауға болады. Соңғы деңгей – Рид-Соломон коды. Рид-Соломон кодтары қателерден қалпына келтіру мүмкіндігі жағынан оңтайлы, бірақ жасау және қалпына келтіру процесі баяу. Әр деңгейдегі блоктардың саны алдыңғы деңгейге қарағанда азайғандықтан, Рид-Соломон кодында қалпына келтіруге қажетті блоктардың саны аз. Осылайша, Рид-Соломон коді баяу болғанымен, оның өңдеуі қажетті дерек көлемі шағын. Қалпына келтіру кезінде ең алдымен Рид-Соломон коды қалпына келтіріледі. Бұл әдіс жұмыс істейтініне кепілдік беріледі, егер соңғы деңгейге дейінгі деңгейдегі жоғалған блоктардың саны соңғы деңгейдегі қазіргі блоктардан кем болса. Төменгі деңгейлерге қарай, LDPC (xor) қалпына келтіру деңгейін төменгі деңгейді қалпына келтіру үшін жоғары ықтималдықпен пайдалануға болады, егер барлық қалпына келтіру блоктары болса және төменгі деңгейде қалпына келтіру деңгейінен кем дегенде C' блоктары жоғалса. Қалпына келтіру алгоритмі – төменгі деңгейден генерациялық жиынының тек біреуі жоқ қалпына келтіру блогын табу. Содан кейін, қалпына келтірілген блоктың xor нәтижесі барлық қазіргі блоктармен есептелгенде, жоғалған блок табылады.

The input data is divided into blocks. Blocks are sequences of bits that are all the same size. Recovery data uses the same block size as the input data. The erasure of a block (input or recovery) is detected by some other means. (For example, a block from disk does not pass a CRC check or a network packet with a given sequence number never arrived.) The number of recovery blocks is given by the user. Then the number of levels is determined along with the number of blocks in each level. The number in each level is determined by a factor B which is less than one. If there are N input blocks, the first recovery level has B*N blocks, the second has B*B*N, the third has B*B*B*N, and so on. All levels of recovery except the final one use an LDPC, which works by xor (exclusive or). Xor operates on binary values, 1s and 0s. A xor B is 1 if A and B have different values and 0 if A and B have the same values. If you are given result of (A xor B) and A, you can determine the value for B. (A xor B xor A = B) Similarly, if you are given result of (A xor B) and B, you can determine the value for A. This extends to multiple values, so given result of (A xor B xor C xor D) and any 3 of the values, the missing value can be recovered. So the recovery blocks in level one are just the xor of some set of input blocks. Similarly, the recovery blocks in level two are each the xor of some set of blocks in level one. The blocks used in the xor are chosen randomly, without repetition. However, the number of blocks xor'ed to make a recovery block is chosen from a very specific distribution for each level. Since xor is a fast operation and the recovery blocks are an xor of only a subset of the blocks in the input (or at a lower recovery level), the recovery blocks can be generated quickly. The final level is a Reed–Solomon code. Reed–Solomon codes are optimal in terms of recovering from failures, but slow to generate and recover. Since each level has fewer blocks than the one before, the Reed–Solomon code has a small number of recovery blocks to generate and to use in recovery. So, even though Reed–Solomon is slow, it only has a small amount of data to handle. During recovery, the Reed–Solomon code is recovered first. This is guaranteed to work if the number of missing blocks in the next to final level is less than the present blocks in the final level. Going lower, the LDPC (xor) recovery level can be used to recover the level beneath it with high probability if all the recovery blocks are present and the level beneath is missing at most C' fewer blocks than the recovery level. The algorithm for recovery is to find some recovery block that has only one of its generating set missing from the lower level. Then the xor of the recovery block with all of the blocks that are present is equal to the missing block.

Патент мәселелері

Торнадо кодтары бұрын Америка Құрама Штаттарында патенттелген. US6163870 A (1997 жылдың 6 қарашасында тіркелген) және US 6081909 A (1997 жылдың 6 қарашасында тіркелген) патенттері Торнадо кодтарын сипаттайды және олардың патенттік мерзімі 2017 жылдың 6 қарашасында аяқталды. US6307487 B1 (1999 жылдың 5 ақпанында тіркелген) және US6320520 B1 (1999 жылдың 17 қыркүйегінде тіркелген) патенттерінде де Торнадо кодтары туралы айтылған, олардың патенттік мерзімі тиісінше 2019 жылдың 5 ақпанында және 2019 жылдың 17 қыркүйегінде аяқталды.

Цитаталар

Майкл Люби Торнадо кодтарын ойлап тапты.