Binary Reed–Solomon encoding

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Binary Reed–Solomon coding (BRS), which belongs to a RS code, is a way of encoding that can fix node data loss in a distributed storage environment. It has maximum distance separable (MDS) encoding properties. Its encoding and decoding rate outperforms conventional RS coding and optimum CRS coding.

Binary Reed–Solomon coding (BRS), which belongs to a RS code, is a way of encoding that can fix node data loss in a distributed storage environment. It has maximum distance separable (MDS) encoding properties. Its encoding and decoding rate outperforms conventional RS coding and optimum CRS coding.

Equally divides the original data blocks into blocks, and each block of data has -bit data, recorded as S=(s_0,s_1,...,s_{k-1}) where s_i=s_{i,0}s_{i,1}...s_{i,L-1} , i=0,1,2,...,k-1 . Builds the calibration data block M , M has a total of n-k blocks: M=(m_0,m_1,...,m_{n-k-1}) where m_i=\sum_{j=0}^{k-1}s_j(r_j^i) , i=0,1,...,n-k-1 .

The addition here are all XOR operation, where r_j^i represents the number of bits of "0" added to the front of the original data block s_j . Thereby forming a parity data block m_i . r_j^i is given by the following way: (r_0^a,r_1^a,...,r_{k-1}^a)=(0,a,2a,...(k-1)a) where a=0,1,...n-k-1 . Each node stores data, nodes N_i(i=0,1,...,n-1) store the data as s_0,s_1,...,s_{k-1},m_0,m_1,...,m_{n-k-1} .

If now n=6,k=3 , there ID_0=(0,0,0) , ID_0=(0,1,2) , ID_0=(0,2,4) . The original data block are s_i=s_0,s_1,...,s_{L-1} , where i=0,1,...,k-1 . The calibration data for each block are m_i=m_{i,0}m_{i,1}...mx_{i,L+i\times(k-1)-1} , where i=0,1,...,k-1 .

Calculation of calibration data blocks is as follows, the addition operation represents a bit XOR operation: m_0=s_0(0)\oplus s_1(0)\oplus s_2(0) , so m_0=(m_{0,0}m_{0,1}...m_{0,5}) m_1=s_0(0)\oplus s_1(1)\oplus s_2(2) , so m_1=(m_{1,0}m_{1,1}...m_{1,7}) m_2=s_0(0)\oplus s_1(2)\oplus s_2(4) , so m_2=(m_{2,0}m_{2,1}...m_{2,9}) In the structure of BRS code, we divide the original data blocks into k blocks. They are S=(s_0,s_1,...,s_{k-1}) .

And encoding has been n block calibration data blocks, there are M=(m_0,m_1,...,m_{n-k-1}) . During the decoding process, there is a necessary condition: The number of undamaged calibration data blocks have to be greater than or equal to the number of the original data blocks that missing, if not, it cannot be repaired.

The following is a decoding process analysis: Might as well make n=6 , k=3 . Then m_0=s_0+s_1+s_2 m_1=s_0+xs_1+x^2s_2 m_1=s_0+x^2s_1+x^4s_2 Supposed s_0 is intact, s_1,s_2 miss, choose m_1 , m_2 to repair, make m_1^*=m_1+s_0 m_2^*=m_2+s_0 Because m_1 , m_2 , s_0 are known, m_1^* , m_2^* are known.

So that s_{1,i-2}=m_{2,i}^*+s_{2,i-4} s_{2,i-2}=m_{1,i}^*+s_{1,i-1} According to the above iterative formula, each cycle can figure out two bit values ( s_1,s_2 can get a bit). Each of the original data block length ( L bit), so after repeating L times, We can work out all the unknown bit in the original data block. by parity of reasoning, we can completed the data decoding.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375542352 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.