Patent GB-1385302-A (GB)
Title: Error-detecting decoding device of the weighting and feed-back type
IPC: H04L1/00
Filed: 1973-01-04
Abstract: 1385302 Error correction THOMSON-CSF 4 Jan 1973 [7 Jan 1972 8 Dec 1972] 651/73 Heading G4A A feedback type error detecting/correcting system is described employing digital modulo 2 and algebraic adders for use with received data in a systematic, recurrent, binary code adapted for threshold decoding, i.e. a binary code having data and parity check bits, the latter being formed by the modulo 2 sum of predetermined data bits such that, for each data bit, there exist 2 different modulo 2 sums each including a check bit and the data bit in question, no other data bit appearing in more than one of the q sums, and each received bit being associated with a likelihood value V α  log m [(1-P)/P] where P is the probability of the bit being erroneous, the system being arranged to derive for each received data bit a corresponding corrected bit and its likelihood.  Theory.-The data consists of a series of data bits b i  and associated check bits f i  formed by the known device shown in Fig. 1. The data bits b i  are shifted through a shift register by shift pulses T applied at input 12 such that at a given time t n  = t 0  + nT bit b n  occupies stage 0, bit b n+1  stage 1 and so on, bit b n+9  occupying stage 9 and bit b n-1  having just left stage 0. At each shift pulse two its are transmitted, e.g. at time t n  bits b n+9  and p n+9 , where p n+9  is the following modulo 2 sum formed in adder 16 which comprises three two-bit adders in series:- At the decoder the received bits b i  and p i  correspond to the transmitted bits b i  and p i  and may or may not be equal to b i  and p i  depending on whether an error has occurred. A decision is made as to whether each b i  is erroneous and a decoded bit b i <SP>11</SP> formed accordingly. The syndrome:- is zero if none of its five constituent bits are erroneous and 1 and 0 respectively for odd and even numbers of errors. Three other syndromes each containing b<SP>1</SP> n  exist as follows:- The above four syndromes form a set associated with b<SP>1</SP> n  since each contains b<SP>1</SP> n , no other b<SP>1</SP> appearing in more than one of the syndromes, and each individual syndrome forms a part of three other sets each of which is associated with a respective one of the bits b<SP>1</SP> in that syndrome. Thus for each data bit b n  there exist at the decoder five independent estimates of that bit, viz.  all the R's being independent of b<SP>1</SP> n  and of each other.  Associated with each received bit is a likeli- .hood value V chosen such that V = log m [(1-))/P] where P is the probability of the associated bit being erroneous and m is arbitrary. The likelihood may have a fixed value determined by the nature (in respect of their liability to error) of the encoder and decoder and the connection therebetween. The nature of V is such that given h estimates that a bit x = 0 with associated likelihoods V 1 <SP>0</SP>, V 2 <SP>0</SP>..., V h <SP>0</SP>, and k estimates that x = 1 with likelihoods V 1 <SP>1</SP>, V 2 <SP>1</SP> ..., V k <SP>1</SP>, then the likelihood that x = 0, V(x = 0), is given by the following algebraic sum:- This procedure is applied in a first embodiment to the five replicas associated with each bit by forming the algebraic sum of their likelihoods, each of which is given a sign in accordance with the binary value of the associated replica. The bit associated with the five replicas is then assigned a binary value in accordance with the sign of the likelihood sum and a likelihood in accordance with the value of that sum. In this embodiment the parity bits and their associated likelihoods remain unchanged which can lead to errors if the majority of the parity bits in the replicas associated with a particular data bit are themselves erroneous. This is overcome in a second embodiment by utilizing only the replicas R n,n+3 ; R n,n+5 ; and R n,n+9  in the decision on the value of bit b n , the remaining replicas b<SP>1</SP> n  and R n , n  being used in an analogous fashion to perform a weighted decoding of the parity bit p n . To perform this decision the replicas p<SP>1</SP> n  and D n , n  are used where:- i.e. by substituting b<SP>1</SP> n  for p n  in R n , n . The arrangement is of the feedback type in the sense that whenever a bit b<SP>11</SP> i  is derived for a corresponding received bit b<SP>1</SP> i , the replicas are updated by substituting b<SP>11</SP> i , for b<SP>1</SP> i . Thus at time t n  the replicas are given by:- since for all b<SP>1</SP> i  where i<n there exists a corresponding value b<SP>11</SP> i  whereas no such corresponding value exist for i#n. The same procedure is used for p<SP>11</SP> i  in the second embodiment. Embodiments.-The first embodiment is shown in Fig. 2 where the bits b<SP>1</SP> i  are received at 24 for shift register 25, the bits p<SP>1</SP> i  at 23 for shift register 45, and the likelihoods of bits b<SP>1</SP> i  and p<SP>1</SP> i  at 224 and 223 respectively for shift registers 226 and 245, the decoded bits b<SP>11</SP> i  and their likelihoods being stored in shift registers 55 and 255. Each stage of registers 25, 45 and 55 holds a single bit while each stage of registers 225, 245, and 255 holds a number of bits (e.g. 4) to represent the likelihoods. A number of modulo 2 adders 36-39 form the replicas R which, together with the bit b<SP>1</SP> n  from stage 0 of shift register 25, are applied to inputs 61 of adder 60 to form sign bits or the likelihoods of the replicas, formed by adders 236-239 (see below), and the likelihood of the bit b n <SP>1</SP> from stage 0 or register 225. The likelihood signals are applied to inputs 62 of adder 60 whose outputs 71 and 72 supply, respectively, the sign of the algebraic sum of the likelihoods, forming the decoded value of b n <SP>1</SP> (i.e. b n <SP>11</SP>) and the value of the algebraic sum, forming the likelihood of b n <SP>11</SP>. A second exactly similar stage 100 is provided for a second iteration, it . being stated that the registers 55 and 255 could form the registers in stage 100 analogous to the registers 25 and 225 shown.  The second embodiment, illustrated in Fig. 4 (not shown), is analogous to that shown in Fig. 2, except that two adders (160 and 260) replace adder 60 and the interconnections are somewhat different in order to enable a decision to be made on the correctness of the received check bits p<SP>1</SP> i . Further details: the Specification treats in some detail the theory involved in using approximations for the likelihood values, e.g. restricting the likelihoods to integer values. The adders 236-239 used to calculate the likelihood values of the replicas R are described with reference to Fig. 3. The likelihood values for the terms of the replicas R (supplied as 4 parallel bits by the appropriate stages of registers 225, 245, and 255), are fed via inputs 81-84 to decoders 91-94 having 15 outputs corresponding to the allowed integer values of the likelihoods. The decoder outputs are fed to respective encoders 101-104 each having 16 outputs supplying a number associated with the respective input integer value (the theory behind the choice of the number being given). The numbers are supplied to an adder 105 which supplies a threshold comparator 106 whose output produces a four digit binary value which is supplied to the adder 60. Modification.-As stated above full details of the approximations used are given, it being stated that the approximation using integer values enables the adders 236-239 to be replaced by memories or pre-wired matrices. It is also stated that the likelihood V 1 , 2 ,..., n of a modulo 2 sum of n terms may be approximated by setting it equal to the smallest likelihood for the individual terms of the sum, comparators being used to find the smallest value.