Mathematics & Computer Science
BCH error-correcting codes
1959-1960R. C. Bose & D. K. Ray-Chaudhuri (with A. Hocquenghem)Information and Control (1960)Diaspora (work abroad)
1959
A family of error-correcting codes (Reed-Solomon codes are a special case).
- Dated
- 1959–1960
- As scholars put it
- 1959-1960
- Originator
- R. C. Bose & D. K. Ray-Chaudhuri (with A. Hocquenghem)
- Source text
- Information and Control (1960)
- Region
- Diaspora (work abroad)
- Discipline
- Mathematics & Computer Science
- Evidence
- Documented
- Confidence
- High
- Verification
- Reference-cited
Adding the right kind of redundancy
Any channel that carries digital data, a radio link, a scratched disc, a worn flash cell, flips some bits. An error-correcting code adds extra, carefully chosen bits to each block of data so that the receiver can work out which bits went wrong and put them right, a step called decoding 6.
A BCH code builds those extra bits out of the algebra of finite fields. Each block is treated as a polynomial, and every valid codeword must vanish at a run of consecutive powers of a fixed element of the field. The length of that run sets a "designed distance", and with it a guaranteed number of correctable errors: a binary BCH code of length 15 can be tuned to fix two, three or seven errors depending on how much redundancy you accept 2. That ability to dial in the strength of the code, rather than discovering it afterwards, was the new thing 26.
From experimental design in Calcutta to codes in Chapel Hill
Raj Chandra Bose was born in 1901 in Hoshangabad and trained in Delhi and Calcutta, where he took a first-class MA in pure mathematics in 1927 3. At P. C. Mahalanobis's Indian Statistical Institute in the 1930s he worked on block designs and finite geometries, the arithmetic of arranging agricultural trials 3. He moved to the University of North Carolina at Chapel Hill as a professor in March 1949 3.
Dijen Ray-Chaudhuri, born in 1933, took his MSc at Calcutta's Rajabazar Science College in 1956 and then followed the path to Chapel Hill, finishing a PhD in combinatorics under Bose in 1959 4. Their joint paper on a class of error-correcting binary group codes appeared in Information and Control in 1960 1. Ray-Chaudhuri went on to chair the mathematics department at Ohio State and, with his student R. M. Wilson, to solve Kirkman's schoolgirl problem 4.
A shared discovery
The French mathematician Alexis Hocquenghem (1908-1990) had published the same family of codes in "Codes correcteurs d'erreurs" in the Paris journal Chiffres in September 1959 5. Bose and Ray-Chaudhuri found them independently and published shortly after 25. The codes are named for all three, Bose, Chaudhuri and Hocquenghem, though the C takes only the second half of Ray-Chaudhuri's surname 2.
That is why this entry carries a caveat. The idea was not uniquely Indian, and the Indian-born authors did the work at an American university 34. What is fair to say is that the combinatorial training Bose built in Calcutta, and passed on to his student, is what they brought to the problem.
In discs, drives and QR codes
Practical decoders followed quickly. The standard method computes "syndromes" from the received block, finds an error-locator polynomial, often with the Berlekamp-Massey algorithm, and solves it to find where the errors are 2. Reed-Solomon codes, which work on whole bytes rather than bits, can be seen as a special case of the BCH construction 6.
Between them these codes have protected data on satellite links, compact discs, DVDs, disk drives, USB sticks and solid-state drives, and a BCH code guards the format information in every QR code 2. For years BCH was the usual choice in NAND flash controllers; as denser chips grew noisier, controllers have shifted toward LDPC codes for the most crowded cells 7.
Background
Raj Chandra Bose had built a career in Calcutta on the combinatorics of experimental design before moving to the University of North Carolina at Chapel Hill in 1949. There, with his doctoral student Dijen Ray-Chaudhuri, he turned those finite-field methods to the new problem of correcting errors in transmitted data, publishing in Information and Control in 1960, months after Alexis Hocquenghem had found the same codes in France.
Significance
BCH codes let an engineer choose in advance how many errors a code must correct, and come with efficient algebraic decoders. They, and the Reed-Solomon codes that belong to the same family, have protected data on CDs, DVDs, disk drives, flash memory, satellite links and the format strip of every QR code.
Meanwhile in the West
Hocquenghem found them independently in France.
Fair to say
Co-discovered independently; the Indian-born authors were working in the US.
Path to modern innovation
Used in storage, satellites and digital communications.
Builds on
Transmission
Work done at the University of North Carolina (diaspora).
References
- 1Bose & Ray-Chaudhuri (1960)
- 6A Short Course on Error-Correcting Codes
Further reading
Related
Corrections and additional sources: edit IND-255 on GitHub.