Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!decwrl!hayes.fai.alaska.edu!accuvax.nwu.edu!nucsrl!telecom-request From: rpw3%rigden.wpd@sgi.com (Rob Warnock) Newsgroups: comp.dcom.telecom Subject: Re: Motorola Wristwatch Pager (Looking for Golay Spec) Message-ID: <10442@accuvax.nwu.edu> Date: 4 Aug 90 11:37:29 GMT Sender: news@accuvax.nwu.edu Reply-To: Rob Warnock Organization: Silicon Graphics Inc., Mountain View, CA Lines: 62 Approved: Telecom@eecs.nwu.edu X-Submissions-To: telecom@eecs.nwu.edu X-Administrivia-To: telecom-request@eecs.nwu.edu X-Telecom-Digest: Volume 10, Issue 541, Message 5 of 10 In article <10398@accuvax.nwu.edu> CRW@icf.hrb.com (Craig R. Watkins) writes: | I've been looking for spec of GSC (Golay Sequential Code). Anyone | have any pointers? I suspect that what I am about to say will be of no use as far as pointing you at a spec for the GSC as used by pagers, but for those interested in error-correcting codes in general... From Lin & Costello, "Error Control Coding", (P-H 1983) p.134ff: "THE GOLAY CODE "The (23,12) Golay code is the only known multiple-error-correcting binary perfect code which is capable of correcting any combination of three or fewer random errors in a block of 23 digits. This code has abundant and beautiful algebraic structure. Since its discovery by Golay in 1949, it has become a subject of study by many coding theorists and mathematicians.... "The (23,12) Golay code is either generated by g1(X) = 1 + X^2 + X^4 + X^5 + X^6 + X^10 + X^11 or by g1(X) = 1 + X + X^5 + X^6 + X^7 + X^9 + X^11 "Both g1(X) and G2(X) are factors of X^23 + 1 = (1 + X)g1(X)g2(X). The encoding can be accomplished by an 11-stage shift register with feedback connections according to either g1(X) or g2(X). "...There are several practical ways to decode the (23,12) Golay code up to its error-correcting capacity t=3. two of the best are discussed in this section. Both are refined error-trapping schemes." They go on to describe a version of the Kasami decoder and the systematic search decoder, with plusses and minuses for each. Elsewhere in the book they note that the (23,12) Golay code and the (2^N - 1, 2^N - N - 1) Hamming single-error correcting codes are the only known perfect binary error-correcting codes. The only known perfect non-binary error correcting codes are the general- ized Hamming codes and the double-error-correcting (11,6) code over GF(3), also discovered by Golay. [Peterson & Weldon, "Error-Correcting Codes", (MIT 1972), p.143] "There are a number of results indicating that perfect codes are scarce, and it even seems quite likely that there are no others." [Ibid., p.121] For those who wonder how this connects with pagers, note that by doubling (well, 23/12'ths) the number of bits sent and using the above Golay code, you can get nearly error-free reception with bit error rates approaching 10%. (Occasionally more than three errors will occur in a block of 23 bits, then the whole 12-bit data byte is garbled.) Not bad, not bad... Rob Warnock, MS-9U/510 rpw3@sgi.com rpw3@pei.com Silicon Graphics, Inc. (415)335-1673 Protocol Engines, Inc. 2011 N. Shoreline Blvd. Mountain View, CA 94039-7311