Regenerating code (RGC)[1] 


An \([n,k,d,\alpha,\beta,M]\) Regenerating Code \(\mathcal{C}\) is an erasure correcting code that encodes \(M\) symbols from \(GF(q)\) into an \(\alpha \times n\) matrix over \(GF(q)\), with each column of the matrix treated as a coordinate of a codeword.

The code has the following properties. Any \(k\) coordinates of the codeword can be used to recover the original \(M\) symbols. Any erased coordinate, i.e., the \(\alpha\) symbols of that coordinate, can be recovered by contacting any \(d\) other coordinates and collecting \(\beta\) symbols from each one of them, where \(k \le d \le n-1\) and \(\beta \le \alpha\).

The connection of such codes to distributed storage is as follows. A file of size \(M\) symbols is encoded using the code, and the \(\alpha\) symbols of each coordinate are stored in geographically separated storage nodes. Accessing any \(k\) such nodes gives back the original file. Node failures are considered erasures in the codeword, and any such failed node can be regenerated by contacting \(d\) surviving nodes and downloading \(\beta\) symbols from each of them.


Corrects upto \(n-k\) erasures on coordinates. For standard erasure codes, like Reed-Solomon, total download bandwidth for recovery of a single node is \(k\alpha\) due to the MDS property. For regenerating codes, it is \(d\beta\) which can be significantly less. It was shown by network coding arguments that \(M \le \sum_{i=0}{k-1}\min\{\alpha,(d-i)\beta\}\). Depending on the relative values of \(\alpha\) and \(\beta\), a trade-off between storage per node and download bandwidth arises. Two extreme points of this trade-off curve are the MBR (\(\alpha = d\beta\)) and MSR (\(\alpha = (d-k+1)\beta\)) codes.


If the recovered symbols are exactly equal to the erased symbols, the repair is called an exact repair.If the recovered symbols are not exactly equal to the erased symbols but still preserve the code properties, the repair is called a functional repair.




A. G. Dimakis et al., “Network Coding for Distributed Storage Systems”, IEEE Transactions on Information Theory 56, 4539 (2010) DOI
Page edit log

Your contribution is welcome!

on (edit & pull request)— see instructions

edit on this site

Zoo Code ID: regenerating

Cite as:
“Regenerating code (RGC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024.
@incollection{eczoo_regenerating, title={Regenerating code (RGC)}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Regenerating code (RGC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024.