The Golay codes are examples of perfect codes; they were discovered by the Swiss mathematician and information theorist, Marcel J. E. Golay in 1949. A binary Golay code is a type of linear error-correcting code used in digital communications. The Voyager 1 and 2 spacecraft were launched towards Jupiter and Saturn in 1977. This code was used in the encoding and decoding of the general science and engineering (GSE) data for the missions. It indicated to him that the possibility of a (23, 12) perfect binary code existed that could correct 3 or fewer errors. This led to the binary form of the Golay code. It is one of the few examples of a nontrivial perfect code. This is the only known code capable of correcting any combination of three or fewer random errors in a block of 23 elements. Binary Golay Codes. There are two closely related binary Golay codes. The extended binary Golay code G24 is a [ 24 , 12 , 8 ] code that encodes 12 bits of data in a 24-bit word in such a way that any 3-bit errors can be corrected or any 7-bit errors can be detected. The other, the perfect binary Golay code, G23 is a [ 23 , 12 , 7 ] code that has codewords of length 23 and is obtained from the extended binary Golay code by deleting one coordinate position (conversely, the extended binary Golay code is obtained from the perfect binary Golay code by adding a parity bit). The fact that the extended Golay code is used more often that the Golay code.
STEP 1. Compute the syndrome: s = mod ( w Gt, 2 ) STEP 2. If the weight of s is less than or equal to (3), then the error pattern is: u = [ s , 0 0 0 0 0 0 0 0 0 0 0 0 ] . STEP 3. If the weight of s is greater than (3), but for some i = 1, 2, . . . , 12, the weight of s + Ai is less than or equal to (2), then the error pattern is u = [ s + Ai, ei], where ei is the ith row of the 12 × 12 identity matrix. Step 4. Compute the second syndrome s2 = s A. Step 5. If the weight of s2 is less than or equal to (3) , then the error pattern is:u = [0 0 0 0 0 0 0 0 0 0 0 0 , s2 ] . STEP 6. If the weight of s2 is greater than (3) , but for some i = 1, 2, . . . , 12, the weight of s2 + Ai is less than or equal to (2), then the error pattern is u = [ ei , , s2 + Ai],. STEP 7. If u is not yet determined then request retransmission.
library(expm)## Loading required package: Matrix##
## Attaching package: 'expm'## The following object is masked from 'package:Matrix':
##
## expmI10=diag(10)
Z10=rep(0,10)
z1=rbind(Z10,I10)
z2=c(1,rep(0,10))
P=cbind(z1,z2)x=c(1,1,0,1,1,1,0,0,0,1,0)
A11<-matrix(ncol=11, nrow=11)
for(i in 1:11){
A11[i,] <- x%*%(P%^%(i-1))
}
J11=rep(1,11)
A12=rbind(A11,J11)
J12=c(rep(1,11),0)A=cbind(A12,J12)
A## J12
## 1 1 0 1 1 1 0 0 0 1 0 1
## 1 0 1 1 1 0 0 0 1 0 1 1
## 0 1 1 1 0 0 0 1 0 1 1 1
## 1 1 1 0 0 0 1 0 1 1 0 1
## 1 1 0 0 0 1 0 1 1 0 1 1
## 1 0 0 0 1 0 1 1 0 1 1 1
## 0 0 0 1 0 1 1 0 1 1 1 1
## 0 0 1 0 1 1 0 1 1 1 0 1
## 0 1 0 1 1 0 1 1 1 0 0 1
## 1 0 1 1 0 1 1 1 0 0 0 1
## 0 1 1 0 1 1 1 0 0 0 1 1
## J11 1 1 1 1 1 1 1 1 1 1 1 0I=diag(12)
G=cbind(I,A)
G## J12
## 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 1
## 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1
## 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 1
## 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1
## 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1
## 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1
## 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1
## 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 1
## 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 1
## 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 0 1
## 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1
## J11 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0H=t(G)
H## J11
## 1 0 0 0 0 0 0 0 0 0 0 0
## 0 1 0 0 0 0 0 0 0 0 0 0
## 0 0 1 0 0 0 0 0 0 0 0 0
## 0 0 0 1 0 0 0 0 0 0 0 0
## 0 0 0 0 1 0 0 0 0 0 0 0
## 0 0 0 0 0 1 0 0 0 0 0 0
## 0 0 0 0 0 0 1 0 0 0 0 0
## 0 0 0 0 0 0 0 1 0 0 0 0
## 0 0 0 0 0 0 0 0 1 0 0 0
## 0 0 0 0 0 0 0 0 0 1 0 0
## 0 0 0 0 0 0 0 0 0 0 1 0
## 0 0 0 0 0 0 0 0 0 0 0 1
## 1 1 0 1 1 1 0 0 0 1 0 1
## 1 0 1 1 1 0 0 0 1 0 1 1
## 0 1 1 1 0 0 0 1 0 1 1 1
## 1 1 1 0 0 0 1 0 1 1 0 1
## 1 1 0 0 0 1 0 1 1 0 1 1
## 1 0 0 0 1 0 1 1 0 1 1 1
## 0 0 0 1 0 1 1 0 1 1 1 1
## 0 0 1 0 1 1 0 1 1 1 0 1
## 0 1 0 1 1 0 1 1 1 0 0 1
## 1 0 1 1 0 1 1 1 0 0 0 1
## 0 1 1 0 1 1 1 0 0 0 1 1
## J12 1 1 1 1 1 1 1 1 1 1 1 0J=matrix(rep(1,12),ncol=1,nrow=12)The received codeword: (1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0,1,0)
# the received codeword:
wa1=c(1,0,1,1,1,1,1,0,1,1,1,1)
wa2=c(0,1,0,0,1,0,0,1,0,0,1,0)
wa=c(wa1,wa2)sa=wa%*%H%%2
sa## J11
## [1,] 1 0 0 0 0 0 0 0 0 0 0 1wta=sa%*%J
wta## [,1]
## [1,] 2ua=c(sa,rep(0,12))
ua## [1] 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0va=matrix((ua+wa)%%2)
va## [,1]
## [1,] 0
## [2,] 0
## [3,] 1
## [4,] 1
## [5,] 1
## [6,] 1
## [7,] 1
## [8,] 0
## [9,] 1
## [10,] 1
## [11,] 1
## [12,] 0
## [13,] 0
## [14,] 1
## [15,] 0
## [16,] 0
## [17,] 1
## [18,] 0
## [19,] 0
## [20,] 1
## [21,] 0
## [22,] 0
## [23,] 1
## [24,] 0va0=va[1:12]
va0## [1] 0 0 1 1 1 1 1 0 1 1 1 0The received codeword: ( 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1 ,0, 0, 0, 1, 0, 1, 0, 0, 0)
wb1= c( 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1)
wb2= c( 1, 0, 1 ,0, 0, 0, 1, 0, 1, 0, 0, 0)
wb = c(wb1,wb2)
wb## [1] 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0sb=wb%*%H%%2
sb## J11
## [1,] 1 1 0 0 0 1 0 0 1 0 0 1wtb=sb%*%J
wtb## [,1]
## [1,] 5sb = J %*% sb
Rb = (sb+A)%%2nrb = t(Rb %*% J)ub = c(Rb[5,],I[5,])
vb = (wb+ub)%%2Note. Since the algorithm is designed for IMLD (Incomplete Maximum Likelihood Decoding) and G corrects all the error patterns of weight at most 3, only one row of Rb may have weight less than or equal to 3.
vb0=vb[1:12]
vb0## J11
## 0 0 1 0 0 1 0 1 1 1 1 1The received codeword: [ 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 ]
# The received codeword:
wc1 = c( 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 )
wc2 = c( 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1 )
wc = c(wc1,wc2)
wc## [1] 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1sc=wc%*%H%%2
sc## J11
## [1,] 1 1 0 0 0 0 0 1 0 1 0 1nc = sc %*% J
nc## [,1]
## [1,] 5Sc = J %*% sc
Rc = (Sc+A)%%2nrc = t(Rc %*% J)
nrc## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
## [1,] 4 8 4 4 4 4 8 6 6 6 8 8sc2 = (sc%*%A)%%2
sc2## J12
## [1,] 0 0 0 0 0 0 0 1 1 1 0 0nc2=sc2%*%J
nc2## [,1]
## [1,] 3uc = c(rep(0,12),sc2)
vc = (wc + uc)%% 2
vc## [1] 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1vc0=vc[1:12]
vc0## [1] 1 1 1 0 0 0 0 0 0 0 0 0