Two-dimensional Interleaving Schemes With Repetitons

This thesis proposes an interleaving scheme with two repetitions for correcting burst errors in two-dimensional arrays.Burst errors are continuous errors in clusters or blocks data with arbitrary shapes,which often occur when there is signal interference in data transmission.Interleaving is a technique which can effectively disperse errors or missing consecutive codewords in information and restore information by using ECC.The repetitions is the number of errors corrected of ECC.Considering a two-dimensional array of n x n,it is assumed that each data page contains a fixed number of,say n,codewords with each codeword consisting of n code symbols and capable of correcting two random errors which means that any two symbols in each codeword can be corrected when burst errors occur.The goal is to disperse these code symbols of the same codeword in the array as far as possible.So that in a burst error of size t,there are at most two of the same codeword.This can also be explained that the tristance between any three symbols in each codeword is not less than t,so that ECC with two errors correction capability can be used for error correction.The distance of any two symbols is measured by the L1-distance.Here,the tristance is used to measure the distance of three symbols,which is one smaller than the size of the smallest connected set containing these three symbols.We use the maximum error correction size of the array,or the minimum tristance of any three symbols of the same codeword to determine the effect of interleaving with two repetitions,which is recorded as the interleaving strength.The previous interleaving with repetitions often adopts the lattice interleaving method which considers the lower boundary of n under any interleaving tristance.We consider the boundary of optimal interleaving tristance of arbitrary size n x n arrays.In order to obtain the upper boundary of optimal interleaving tristance,Ad is introduced.It is the largest connected subset on Z2,which satisfies any tristance between three elements should not be larger than d.Using the size of |Ad|,the upper boundary of the optimal interleaving tristance on the n × n array is obtained as Ti=(?).In other words,any interleaving tristance of the n × n array satisfies t ≤T1.This thesis introduce cyclic shifting scheme,which is the circular horizontal translation is performed on each row of the array with several distances.This method can disperse the symbols of the same codewords in the array.We obtain the equal cyclic translation parameter through the decision inequality group of the interleaving tristance,so that the interleaving with two repetitions can be performed well on any size array.On some arrays of certain size,by using unequal circulation,a higher interleaving tristance is obtained.Specific interleving scheme defines lower boundary of the optimal interleaving tristance with two repetitions t≥ T2=(?).