/// ESSA TR ERL 174- ITS 111 A UNITED STATES DEPARTMENT OF COMMERCE PUBLICATION ESSA Technical Report ERL 174-ITS 111 U.S. DEPARTMENT OF COMMERCE Environmental Science Services Administration Research Laboratories Exhaustive Search for the Best Cyclic (20, 8) Code L. R. ESPELAND M. NESENBERGS BOULDER, COLO. APRIL 1970 ESSA RESEARCH LABORATORIES The mission of the Research Laboratories is to study the oceans, inland waters, the lower and upper atmosphere, the space environment, and the earth, in search of the under- standing needed to provide more useful services in improving man's prospects for survival as influenced by the physical environment. Laboratories contributing to these studies are: Earth Sciences Laboratories: Geomagnetism, seismology, geodesy, and related earth sciences; earthquake processes, internal structure and accurate figure of the Earth, and distribution of the Earth's mass. Atlantic Oceanographic and Meteorological Laboratories: Oceanography, with emphasis on the geology and geophysics of ocean basins, oceanic processes, sea-air interactions, hurricane research, and weather modification (Miami, Florida). Pacific Oceanographic Laboratories: Oceanography; geology and geophysics of the Pacific Basin and margins; oceanic processes and dynamics; tsunami generation, propaga- tion, modification, detection, and monitoring (Seattle, Washington). Atmospheric Physics and Chemistry Laboratory: Cloud physics and precipitation; chem- ical composition and nucleating substances in the lower atmosphere; and laboratory and field experiments toward developing feasible methods of weather modification. Air Resources Laboratories: Diffusion, transport, and dissipation of atmospheric con- taminants; development of methods for prediction and control of atmospheric pollution (Silver Spring, Maryland). Geophysical Fluid Dynamics Laboratory: Dynamics and physics of geophysical fluid systems; development of a theoretical basis, through mathematical modeling and computer simulation, for the behavior and properties of the atmosphere and the oceans (Princeton, New Jersey). National Severe Storms Laboratory: Tornadoes, squall lines, thunderstorms, and other severe local convective phenomena toward achieving improved methods of forecasting, detecting, and providing advance warnings (Norman, Oklahoma). Space Disturbances Laboratory: Nature, behavior, and mechanisms of space disturb- ances; development and use of techniques for continuous monitoring and early detection and reporting of important disturbances. Aeronomy Laboratory: Theoretical, laboratory, rocket, and satellite studies of the physical and chemical processes controlling the ionosphere and exosphere of the earth and other planets. Wave Propagation Laboratory: Development of new methods for remote sensing of the geophysical environment; special emphasis on propagation of sound waves, and electro- magnetic waves at millimeter, infrared, and optical frequencies. Institute for Telecommunication Sciences: Central federal agency for research and services in propagation of radio waves, radio properties of the earth and its atmosphere, nature of radio noise and interference, information transmission and antennas, and meth- ods for the more effective use of the radio spectrum for telecommunications. Research Flight Facility: Outfits and operates aircraft specially instrumented for re- search; and meets needs of ESSA and other groups for environmental measurements for aircraft (Miami, Florida). ENVIRONMENTAL SCIENCE SERVICES ADMINISTRATION BOULDER, COLORADO 80302 j^-^^i^c ■^'^'[HCE stR'J\^^'^^ U. S. DEPARTMENT OF COMMERCE Maurice H. Stans, Secretary ENVIRONMENTAL SCIENCE SERVICES ADMINISTRATION Robert M. White, Administrator RESEARCH LABORATORIES Wilmot N. Hess, Director ESSA TECHNICAL REPORT ERL 174-ITS 111 Exhaustive Search for the Best Cyclic |20, 8) Code L. R. ESPELAND M. NESENBERGS INSTITUTE FOR TELECOMMUNICATION SCIENCES BOULDER, COLORADO April 1970 For sale by the Superintendent of Documents, U. S. Government Printing Office, Washington, D. C. 20402 Price 35 cents o o. o =5 Digitized by the Internet Archive in 2012 with funding from LYRASIS IVIembers and Sloan Foundation http://archive.org/details/exhaustivesearchOOespe TABLE OF CONTENTS Page LIST OF FIGURES iv LIST OF TABLES iv ABSTRACT 1 1. INTRODUCTION 1 2. CODE WORD DISTANCE DISTRIBUTION 2 3. WORD ERROR PROBABILITY 8 4. COMPARISON OF (15, 5) AND (20, 8) CODES 11 4.1 Case of Identical Baud (Keying) Speed 11 4.2 Case of Same Transmission Rate 15 5. CONCLUSIONS 17 6. REFERENCES 18 APPENDIX A. Detailed Resiilts - Computation and Tables 19 APPENDIX B. Upper Bounds on Word Error Probability 23 1X1 LIST OF FIGURES Figure Page 1. A shift -register generator showing the feedback connections 3 for the No. 1 (20, 8) code. 2. Distribution of distances for the (15, 5) code and selected 10 (20, 8) codes. 3. Word error probability characteristics for selected 12 (20, 8) codes. 4. Word error probability comparison of the (15, 5) code (P ) 13 and the No. 1 (20, 8) code (P ) at identical baud speeds. 5. Word error probability comparison of the (15, 5) code (P ) 16 with the No. 1 (20, 8) code (P ) at the same transmission rate. e LIST OF TABLES Table 1. Word error probability and code distance structure 5 2. Minimum distance values and selected cases for 14 comparison IV EXHAUSTIVE SEARCH FOR THE BEST CYCLIC (20, 8) CODE L. R, Espeland and M. Nesenbergs An exhaustive computer search for the best, simply implemented, cyclic (20, 8) codes was carried out, and the procedures and results are reported here. Some forty almost equally good (20, 8) codes are identified, but, alas, none of them appear to be better than the familiar (15, 5) Bose -Chaudhuri-Hocquenghena code. 1. INTRODUCTION In the fall of 1969 development was initiated for an efficient medium speed digital transmission scheme using error correcting coding for low power VHF Ionospheric Scatter commiinications in polar regions. Presently, the design and implementation of the one- way error correcting system is nearing completion. The heart of the scheme is an interleaved nearly orthogonal (15, 5) BCH (for Bose- Chaudhuri-Hocquenghem) code of minimum distance 7 (Peterson, 1961) with a generating polynomial / X 5 3 g(x) = X +X +X+1 . The decoder is a classical minimum distance (or codebook, or, under certain normal assumptions, a maxinnum likelihood, or optimum) decoder, that outputs the nearest valid codeword. A number of issues regarding the optimality of the (15, 5) choice were raised because sonne convolutional, or other non-block code, might be better. This is a valid point still being investigated. First, the one -third rate of the code appears a little low. On the other hand, a rate of one -half is likely to be too high to combat the typically bursty and unpredictable errors on a VHF scatter channel. Second, the number of information symbols, k = 5, is not ideally suited for the manipulation of standard codewords of either 7 or 8 bits. Third, the hardware --size, speed, and cost --should be as practical as possible. An alphabet size Q of 2 = 256 and a block size of n = 20 look reasonable. To satisfy items one through three, we have sought and found "the best" (20, 8) block code generated by a simple cyclic generator of eight registers. This report relates how a computer search was carried out and which of the (20, 8) codes are the best. To manipulate and compare different codes, a number of tools were used. The most impor' tant ones were connplete codeword distance distributions for all 7 2 = 128 codes and word error probability bounds for these codes. Finally, the performance of the best cyclic (20, 8) code is compared to that of the (15, 5) BCH code. 2. CODEWORD DISTANCE DISTRIBUTION In this section we explain the distance (or weight) distribution data computed in our search for an attractive (20, 8) code. The com- puted material pertains to a small and quite specific family of (20, 8) codes. We consider only those linear cyclic codes that are easily encoded (e.g. , with the feedback device shown in fig. 1). It is seen from figure 1 that such a (20, 8) code is fully deter- mined by the feedback connections (A A . . . , A ) from the encoder 7 D 1 registers; A. = denotes no connection, and A. = 1 denotes a connection J J from the j -th register to the exclusive - OR gate. There are a total of 7 2 = 128 distinct feedback combinations, including all seven O's and all seven I's. Distinct feedback patterns do not however necessarily imply codes with different distance distributions. For each given code with a generator [A.], there is a conjugate generator [A . ], j = 1, 2, . . . , 7. The conjugate encoder has the reverse order of feedback leads. More- over, some conjugate generators are the same as the original generators, X CO s o s K O K +^ O CO 1) CO "^ O • cs ^ ?S S O i35^ fe4 Clearly, this happens when A. = A . for all j, i.e. , when J o-J 4 while (A , A A A ) are arbitrary; thus, there are 2 =16 invariant conjugates, including all O's and all I's. The remaining [A.] encoders must have distinct conjugates. There are exactly i{128 - 16) = 56 such "encoder and conjugate encoder" pairs. Observe that any code can be viewed as running forward or backward in time. Whatever the code is, a reversal must leave the weight distribution invariant. Yet the code generator, as for our (20, 8) code, must then become the above conjugate, We conclude that there can be no more than 16 + 56 = 72 codes with dis- tinct distance distributions. Among them is the code generated by repe- tition of the eight information bits. This is the trivial "no connection" A = A = . . . = A = case, which we prefer to ignore from now on. There remain 71 codes that are of interest. The distance distributions of all these 71 cases have been computed, and are tabulated (together with other entities) in table 1. See appendix A for background material and details of the computed data. Consider a particular (20, 8) code among the eligible 71. The o code consists of 2 = 256 distinct codewords w , m = 0, 1, . . . , 255. Let d denote the Hamming distance between two codewords w and mn ° m w . We seek the distribution of f d ] (m, n = 0, 1, .... 255) for the n (■ mn-* code at hand, and for the other seventy (20, 8) codes. As is well known (Peterson, 1961), the distance distribution of a linear code is the same as the one for the subset pertaining to a par- ticular reference word, vis, , f d ] for any m . In particular, one ^ "^o^ o Table 1. Word Error Probability and Code Distance Structure CODFtPF-- 3.16-001 1.00-001 3.16-002 1.00-002 1.00-003 1.00-004 647 3.76+001 4.94-001 7.33-003 1.55-004 1.23-007 1.20-010 1 713 MD OF 6 NCW 6 28 39 36 36 36 39 28 6 I 1 ) ♦♦ 711 3.76+001 4.94-001 7.43-003 1.62-004 1.33-007 1.30-010 2 447 MD OF 5 NCW 1 6 19 39 52 42 32 24 19 16 5 677 3.75+001 4.86-001 7.42-003 1.68-004 1.43-007 1.40-010 3 773 MD OF 6 NCW 7 32 27 32 58 32 27 32 7(1) 611 3.75+001 4.89-001 7.52-003 1.69-004 1.43-007 1.40-010 4 443 MD OF 5 NCW 4 5 20 35 40 46 40 35 20 5 4(1) 703H* 3.76+001 4.91-001 7.57-003 1.70-004 1.43-007 1.40-010 5 607 MD OF 6 NCW 7 25 34 44 42 38 36 12 7 9 1 747H* 3.76+001 4.92-001 7.60-003 1.70-004 1.43-007 1.40-010 6 717 MD OF 6 NCW 7 24 35 46 40 38 36 10 9 10 737 3.76+001 4.98-001 7.71-003 1.72-004 1.43-007 1.40-010 7 767 MD OF 6 NCW 7 28 35 36 42 36 35 28 7 (1) 543E* 3.76+001 4.99-001 7.72-003 1.72-004 1.43-007 1.40-010 8 615 MO OF 6 NCW 7 20 39 54 36 30 3? 18 1' 6 557 3.77+001 5.05-001 7.81-003 1.73-004 1.43-007 1.40-010 9 755 MD OF 6 NCW 7 19 41 52 38 34 22 20 19 3 641 3.76+001 5.11-001 8.04-003 1.76-004 1.44-007 1.40-010 10 413 MD OF 5 NCW 2 6 18 47 44 20 44 47 18 6 2 11) 545E* 3.76+001 4.96-001 7.77-003 1.78-004 1.53-007 1.50-010 11 515 MD OF 5 NCW 1 7 22 33 44 52 38 20 19 13 4 2 477B 3.76+001 4.90-001 7.66-003 1.77-004 1.53-007 1.50-010 12 771 MD )F 5 NCW 1 7 24 30 42 54 40 24 13 11 8 1 573C 3.76+001 5.06-001 8.07-003 1.83-004 1.53-007 1.50-010 13 675 MD OF 5 NCW 5 5 11 45 62 22 18 50 29 5 3 661B 3.76+001 4.92-001 7.86-003 1.86-004 1.62-007 1.60-010 14 433 MD OF 6 NCW 8 25 28 46 54 32 26 18 10 7 1 511 3.75+001 4.94-001 7.94-003 1.87-004 1.63-007 1.60-010 15 445 MD OF 5 NCW 6 5 14 35 44 46 44 35 14 5 6(1) 475 3.76+001 5.03-001 8.13-003 1.89-004 1.63-007 1.60-010 16 571 MD OF 5 NCW 2 7 22 35 40 42 40 35 22 7 2 (1) 435E* 3.82+001 5.48-001 8.99-003 2.05-004 1.74-007 1.70-010 17 561 MD OF 5 NCW 1 8 13 49 42 40 42 22 21 8 9 625 3.76+001 4.99-001 8.35-003 2.04-004 1.82-007 1.80-010 18 523 MD OF 5 NCW 6 6 1 3 32 44 52 50 28 6 6 9 3 473 3.76+001 5.05-001 8.45-003 2.06-004 1.82-007 1.80-010 19 671 MD OF 6 NCW 9 28 27 36 54 36 27 28 9 (1) 705 3.77+001 5.08-001 8.51-003 2.06-004 1.83-007 1.80-010 20 507 MD OF 6 NCW 9 24 30 44 50 36 24 20 13 4 1 563 3.76+001 5.18-001 8.79-003 2.10-004 1.83-007 1.80-010 21 635 MD OF 5 NCW 2 8 18 39 44 32 44 39 18 8 2 (1) 623 3.72+001 5.21-001 8.81-003 2.10-004 1.83-007 1.80-010 22 623 MD OF 6 NCW 9 20 38 44 38 44 28 20 9 741 3.76+001 5.07-001 8.67-003 2.15-004 1.92-007 1.90-010 23 417 MD OF 5 NCW 3 8 19 30 39 52 50 28 13 4 3 5 1 631 3.76+001 5.08-001 8,67-003 2.15-004 1.92-007 1.90-010 24 463 MD OF 5 NCW 1 9 19 30 50 50 38 24 13 13 7 1 Table 1 Con't. CODEfPE — 3.16-001 1.00-001 3.16-002 1.00 -002 1.00 -003 1.00-004 25 551E* 455 MD OF 3.76+001 5 NCW 1 5.12-001 9 29 28 8.80-003 32 48 40 2.16 34 -004 23 1.93 7 3 -007 1 1.90-010 26 467 731 MD OF 3.76+001 5 NCW 1 5.19-001 9 21 35 8.95-003 42 38 42 2.18 35 -004 21 1.93- 9 1 -007 ( 1 ) 1.90-010 27 547 715 MD OF 3.75+001 5 NCW 6 5.01-001 7 14 27 8.69-003 44 58 44 2.21 27 -004 14 2.02- 7 6 -007 ( 11 2.00-010 28 527 725 MD )F 3,76+001 5 NCW 2 5.21-001 9 18 35 9.16-003 44 38 44 2.27 35 -004 18 2.03- 9 2 -007 (1) 2.00-010 29 533 665 MD OF 3.77+001 6 NCW 10 5.32-001 20 39 44 9.40-003 28 44 39 2.30 20 -004 10 2.03- ( 1) -007 2.00-010 30 517 745 MD OF 3.76+001 5 NCW 1 5.23-001 10 21 31 9.33-003 42 44 42 2.35 31 -004 21 2.12- 10 1 -007 ( 1 ) 2.10-010 31 6430 613 MD OF 3.76+001 5 NCW 2 5.07-001 10 18 22 9.10-003 52 60 36 2.38- 24 -004 10 2.22- 10 10 -007 1 2.20-010 32 701 407 MD OF 3.76+001 5 NCW 4 5.18-001 10 16 23 9.68-003 44 60 44 2.58 23 -004 16 2.42- 10 4 -007 (1) 2.40-010 33 457 751 MD OF 3.77+001 6 NCW 12 5.39-001 20 31 44 1.02-002 40 44 31 2.64 20 -004 12 2.42- (1 1 -007 2.40-010 34 531 465 MD OF 3.77+001 5 NCW 2 5.34-001 12 18 24 1.03-002 50 50 34 2.79 30 -004 20 2.62- 10 4 -007 1 2.60-010 35 437 761 MD OF 3.77+001 6 NCW 13 5.43-001 20 27 44 1.05-002 46 44 27 2.81- 20 -004 13 2.62- (1) -007 2.60-010 36 541 415 MD OF 3.77+001 6 NCW 13 5.43-001 20 27 44 1.05-002 46 44 27 2.81- 20 -004 13 2.62- (1 ) -007 2.60-010 37 633 663 MD OF 3.76+001 5 NCW 5 5.36-001 11 9 27 1.05-002 50 50 50 2.88- 27 -004 9 2.72- 11 5 -007 (1 ) 2.70-010 38 567E 735 MD OF 3.77+001 5 NCW 5 5.51-001 12 23 23 1.12-002 28 46 48 3.09- 40 -004 23 2.92- 6 1 -007 2.90-010 39 727C 727 MD OF 3.80+001 6 NCW 15 5.98-001 36 29 32 1.22-002 34 32 34 3.27- 16 -004 15 3.03- 12 -007 3.00-010 40 453F 651 MD OF 3.83+001 6 NCW 16 6.14-001 20 37 28 1.28-002 36 44 34 3.46- 36 -004 4 3.23- -007 3.20-010 41 667 733 MD )F 3.77+001 5 NCW 6 5.64-001 14 20 17 1.23-002 32 52 44 3.53- 38 -004 26 3.41- 6 -007 3.40-010 42 575 575 MD OF 3.72+001 5 NCW 6 5.50-001 15 8 13 1.23-002 50 55 56 3.66- 42 -004 2 3.60- 1 -007 3.60-010 6 1 43 645 513 MD OF 3.77+001 5 NCW 6 5.60-001 15 8 13 1.24-002 60 66 24 3.66- 18 -004 30 3.60- 15 -007 3.60-010 44 471/i 471 MD OF 3.81+001 6 NCW 18 6.20-001 30 25 44 1.36-002 36 24 30 3.81- 20 -004 18 3.62- 10 -007 3.60-010 45 605 503 MD OF 3.75+001 4 NCW 1 5.11-001 6 2 14 1.21-002 38 44 44 7.22- 44 -004 38 6.09- 14 2 ■006 6 6.01-008 1 (1) 46 637D 763 MD OF 3.77+001 4 NCW 1 5.28-001 4 5 12 1.30-002 35 52 46 7.59- 44 -004 31 6.13- 8 5 -006 8 6.01-008 4 47 461 431 MD OF 3.75+001 4 NCW 1 5.19-001 5 5 17 1.30-002 26 42 62 7.65- 42 -004 26 6.14- 17 5 -006 5 6.01-008 1 (1) 48 627 723 MD OF 3.76+001 4 NCW 1 5.43-001 2 7 18 1.37-002 34 44 42 7.79- 44 -004 34 6.15- 18 7 -006 2 6.02-008 1 (1) Table 1 Con't. CODEpE— 3.16-001 1.00-001 3.16-002 1.00 -002 1.00- -003 1.00-004 657 3.77+001 5.52-001 1.41-002 7.91 -004 6.16- -006 6.02-008 49 753 Mn OF 4 NCW 1 5 6 21 35 34 36 42 43 25 6 1 617 3.76+001 5.48-001 1.41-002 7.97 -004 6.17- -006 6.02-008 5n 743 MD OF 4 NCW 1 4 7 12 34 48 42 48 34 12 7 4 1 (1) 537F* 3.77+001 5.70-001 1.60-002 8.76 -004 6.26- -006 6.03-008 51 765 MD OF 4 NCW 1 7 10 11 21 48 54 40 33 17 8 5 653 3.76+001 5.48-001 1.82-002 1.34 -003 1.21- -005 1.20-007 52 653 MD OF 4 NCW 2 8 3 8 25 48 66 48 25 8 3 8 2 (1) 535 3.76+001 5.55-001 1.82-002 1.34 -003 1.21- -005 1.20-007 53 565 MD OF 4 NCW 2 3 5 19 25 42 62 42 25 19 5 3 2 (1) 577 3.76+001 5.57-001 1.84-002 1.35 -003 1.21- -005 1.20-007 54 775 Mn OF 4 NCW 2 4 5 16 25 44 62 44 25 16 5 4 2 (1) 673 3.84+001 7.71-001 2.81-002 1.68 -003 1.25- -005 1.20-007 55 673 MD OF 4 NCW 2 16 16 12 25 28 36 44 28 20 20 8 621 3.77+001 5.85-001 2.28-002 1.88 -003 1.81- -005 1.80-007 56 423 MD OF 4 NCW 3 2 3 18 32 44 50 44 32 18 3 2 3 (1) 721 3.84+001 7.28-001 2.77-002 2.03 -003 1.82- -005 1.80-007 57 427 MD JF 4 NCW 3 6 8 26 44 32 28 32 19 26 20 6 5 707 3.87+001 8.74-001 3.96-002 2.87 -003 2.45- -005 2.40-007 58 707 MD OF 3 NCW 4 2 4 22 28 13 28 52 28 13 28 22 4 2 4 (1) 757 3.76+001 6.13-001 3.21-002 3.02 -003 3.00- -005 3.00-007 59 757 MD OF 4 NCW 5 4 20 10 40 96 40 10 20 4 5 (1) 553 3.78+001 6.57-001 3.31-002 3.03 -003 3.00- -005 3.00-007 60 655 MD OF 4 NCW 5 2 16 34 48 44 48 34 16 2 5 (1) 451 3.78+001 6.64-001 3.39-002 3.06- -003 3.00- 005 3.00-007 61 451 MD OF 4 NCW 5 4 16 26 48 56 48 26 16 4 5 (1) 601 3.78+001 6.98-001 3.60-002 3.14- -003 3.01- ■005 3.00-007 62 403 MD OF 3 NCW 2 4 6 5 14 23 30 48 56 44 20 3 555 3.81+001 7.53-001 3.87-002 3.25 -003 3.02- -005 3.00-007 63 555 MD OF 4 NCW 5 4 12 12 10 48 72 48 10 12 12 4 5 ( 1 ) 501 3.79+001 7.71-001 4.41-002 3.84 -003 3.62- ■005 3.60-007 64 405 MD OF 4 NCW 6 12 8 4 9 36 60 60 40 16 4 441 3.80+001 8.07-001 4.87-002 4.38- -003 4.22- -005 4.20-007 65 411 MD OF 4 NCW 7 6 8 8 19 44 36 56 53 14 4 521 3.84+001 8.70-001 5.03-002 4.42- -003 4.22- ■005 4.20-007 66 425 MD OF 3 NCW 2 6 12 7 8 21 42 58 42 21 8 7 12 6 2 ( 1 ) 505 3.87+001 9.54-001 5.71-002 5.04- -003 4.82- ■005 4.80-007 67 505 MD OF 3 NCW 4 6 8 10 16 25 36 44 36 25 16 10 8 6 4 (1) 421 3.89+001 1.04+000 6.23-002 5.24- -003 4.84- ■005 4.80-007 68 421 MD OF 3 NCW 8 4 24 24 6 32 48 24 20 32 24 8 1 525 4.92+001 1.65+000 1.22-001 1.19- -002 1.20- 004 1.20-006 69 525 MD OF 4 NCW 20 110 100 n 25 777 4.01+001 1.52+000 1.28-001 1.26- -002 1.26- 004 1.26-006 70 777 MD )F 4 NCW 21 14 1 35 70 21 7 42 35 2 7 603 3.81+001 9.31-001 9.28-002 2.21- -002 2.02- -003 2.00-004 71 603 MD OF 2 NCW 1 6 6 15 2 27 50 40 50 27 2 15 6 itive binary polynomial 6 1 1 *indicates prim **indicates one code word at distance 20 is justified to pick m = 0, with w the all zero codeword. We let o o d = d and compute the 255 values d for all n = 1, 2, .... 255 non- n o n n zero codewords. For each code, we finally define the "distance distribution" as a set of twenty numbers M{i)(i = l, ...,20), where M(i) is the number of codewords with d = i. While we do refer to appendix B for more details, n it is clear that S M(i) = 255. i For each code, define a nfiininfiunn distance, MD or d , as the o smallest i> for which M(i) > holds. Clearly, the nainiraum distance and the distance distribution must play a role in a search for nmore effective codes (see second lines, table 1). How this connes to pass is the subject of the next section. 3. WORD ERROR PROBABILITY The word error probability, P , is a standard performance cri- terion of a given code under specified conditions (Peterson, 1961; Gallager, 1968). As is always the case, a number of simplifying assump- tions are needed to render the present P computing task tractable. We assume that: (a) The digital commiinications medium is a memoryless binary synnmetric channel (BSC) with bit error (or transition) probability p . (b) The binary message source is completely random., i.e., any source statistic is memoryless, symmetric, and mutually independent. (c) The decoder performs a minimum distance decoding. A decoding error occurs, whenever the received word is at least as far from the transmitted codeword as from any other codeword. Under these assumptions and subject to complete knowledge of codeword distance distribution M(i), an exact computation of word error probability P still represents a cumbersome task. In figure 2 we plot M{i), i = 1, 2, . . . for (15, 5) BCH and selected (20, 8) codes. In appendix B we present and prove two upper bounds on P : "the union bound" P and the "minimum distance bound" Q . Three e e features of the bounds are quite apparent: (a) For p near one-half (i. e. , 10

P = P , e e e e The union bound P therefore is pertinent to our code evaluation, e Since it is a sharp bound, we use it in place of actual word error proba- bility P to assess performance of different codes (see similar argu- ments by Peterson (1961) and Wozencraft and Jacobs (1967)). We hav.e computed P 's (viz., P and Q ) for all 71 structurally distinct cyclic (20, 8) codes, as well as for the (15, 5) code that is being imple mented for the VHF Scatter Channel. The bit error probability values _i _i _3- _2 _3 _4 p = 10 , 10 , 10 ^, 10 ,10 , and 10 were used in the connputation (see app. A and B for details). The bulk results are presented in table 1 with pertinent mininaum distance and distance distribution information. As an example of code perfornnance comparison, consider the -2 -4 column p = 10 in table 1. Code 1 has p = 1. 55(10 ), code 2 has P = 1.62(10" ), and finally code 71 has P =2.21(10" ). One observes that the codes have been numbered in an order of monotonically o o o in 1 1 1 ? -fs H 2§ I I 00 ^ ^ +i vO O C^ CO ^ u S o g o u oo Q) ■^ ■M Q — O I to o V ~ a o o z 2 g o u CO » I I u .og o ■ 65 5.59+00 1.16-01 1.43-03 1.53-05 1.57-09 1.57-13 1 53 MD OF 7 NCW 15 15 (1) 5 5 g^"" 8'^(20, 8)^^e^ 647 6.09-01 2.02-01 4.58-03 9,67-05 7.72-08 7.52-11 2 713 MD OF 6 NCW 6 28 39 36 36 36 39 28 6 ^ _ „ ,_l/5 6/5 ^-^(20,8)^^ Pe ) 9.56-01 2.74-01 1.72-01 9.46-02 647 2.73+01 1.47-01 1.11-03 1.30-05 2.91-09 7.24-13 3 713 MD OF 6 NCW 6 28 39 36 36 36 39 28 6 14 P of (15, 5) with P of (20, 8) or with 5/8 P of the same (20, 8) code, e — e — e The issue depends on the choice of data block size to be used as a "standard word. " Choices of 5, 8, or 5 X 8 = 40 appear plausible. Regardless of one's preference, the (15, 5) code shows a substantial performance advantage over the best of the (20, 8) codes, hence over all cyclic (20, 8) codes. 4. 2 Case of Same Transmission Rate If transmission rates are set equal, baud speeds must differ by the earlier factor of 6/5. Let us assume a specific modem, noncoherent frequency shift keying (NCFSK). The bit error probability is an expo- nential function of the signal power-to-noise power density ratio times the baud time (Lawton, 1958; Wozencraft and Jacobs, 1967). It follows that, if p is the bit error probability for (15, 5) code, (2p ) must e e play the corresponding role for bit error rate in a (20, 8) code. Pre- vious formulas now enable the computation of word error probabilities P . e The computer results for constant transmission rate are pre- sented in table 2 and figure 5. Again, the best (20, 8) code (no. 1) is compared with the (15, 5) BCH code, and the results are rauch more even. -2 At p = 5(10 ) the two systems are indistinguishable. For -2 ® p > 5(10 ) the (15, 5) code shows a slight advantage, while for ® _2 p < 5(10 ) the (20,8) no. 1 code does better. One expects, that for very small p the asymptotic exponential nature of all modems (non- fading channelsl ) would guarantee a considerable superiority for the (20, 8) no. 1 code. 15 10-2 Pe -1 \ 1 IQ-' p 10-2 10'^ Figure 5. Word error probability comparison of the (15,5) code (P ) with the No. 1 (20,8) code (P ) at same transmission rate e e 16 5. CONCLUSIONS The goal of this study was to find the best cyclic, simply genera- ted (20, 8) block codes and to compare their performance with the well known (15, 5) BCH code. A search and performance scrutiny was carried out, and the results were disappointing. The very best (20, 8) code (no. 1 in table 1 with shift register generator 647 or 713, as shown in fig. 1) simply does not outperform the (15, 5) code. In the case (4.1) of identi- cal baud speeds, the (20, 8) is worse. In the case (4.2) of identical data rates the two codes appear evenly matched, and the (20, 8) requires 5/6 less bandwidth. 17 6. REFERENCES Feller, W. (I960), An Introduction to Probability Theory and Its Applications, I, 23, 41-45 (John Wiley & Sons, Inc., New York, N. Y. ). Gallager, R. G. (1968), Information Theory and Reliable Communication, 116-13 5 (John Wiley & Sons, Inc., New York, N.Y.). Lawton, F. G. (19 58), Conaparison of binary data transmission systems. Second National Conference on Military Electronics. Peterson, W. W. (1961), Error-Correcting Codes, 30-47, 107-161, 251-270 (The M. I. T. Press and John Wiley & Sons, Inc. , New York, N. Y. ). Wozencraft, J. M. and I. M. Jacobs (1967), Principles of Communication Engineering, 264-266, 519 -524 (John Wiley & Sons, Inc., New York, N. Y. ). 18 APPENDIX A Detailed Results - Computation and Tables A cyclic code may be generated using a linear feedback shift register circuit (Peterson, 1961). The feedback is formed by an "exclusive OR" (sum modulo 2) gate of certain register stage outputs. These outputs are represented as the nonvanishing terms in a generator polynomial 8 7 1 g(x) = X + A X + . . . + A X + 1 . (A-l) This equation yields a nine -bit representation for the feedback connec- 8 tions in the generator circuit. The first and last (x and 1) coefficients are always unity. The binary number that represents the coefficients has nine digits, or three digits of octal notation (Peterson, 1961). If one reverses the order of the connections, then a new code results; 110 100 111 = 647 HI 001 Oil = 713 . This symmetry yields the same distance structure for both codes; therefore, the number of structurally distinct codes (excluding all 7 zeros) is about half of the total, i.e., ^2 ) = 64. A detailed count reveals 71 distinct cases. The sinnulation of a shift register was done on a CDC 6400 com- o puter. For each code one can easily generate the 2 -1 nonzero combina- tions of the eight information bits and corresponding codewords and the subsequent count of ones in the words relative to the base codeword of all zeros. The count M(i), of codewords at distance i from the all zero word is given in the second line for each code in table 1. For example 1 713 MD OF 6 NOW 6 28 39 36 36 36 39 28 6 (1), where (1) stands for one codeword of weight 20, states that code 647 and 19 713 has a miinimum distance word of 6, and that the number of codewords at distance 6 is 6, at distance 7 is 28, at distance 8 is 39, etc. Some of the code numbers are followed by a letter that has the identical repre- sentation, as in Peterson (1961). The asterisk indicates codes that represent primitive binary polynomials (A-1). The first line for each code of table 1 gives the codeword proba- bility of error (see app, B): f.= f„„„.^,.-,,«-fflf\.(^ I k= (A-2) where Q- i+i and j=l2 (A-3) is computed for each of six discrete values of p listed at the top of e each page of table 1. The union bound nature in (A-2) leads to excessively large P for p aroiindlO" or larger. Another familiar upper bound, the mini- e mum distance bound, is used (see app, B): -1 Q = 1 e I (^K n= (1-Pe) N -n (A-4) 20 This leads to the same expression Q for certain pairs of mini - e mum distance values d , For example, = [B] = 3 and therefore d = 4 o o and d = 5 have identical Q values. The least of the two bounds o e (P and Q ) is clearly the best and should be used, e e In table 2 we find the first entries are the Q (A -4) bounds that e are based on minimum distance properties of the code. Note that the last row applies to the (15, 5) BCH code only. Later entries in the table show additional word error probability connputations presented in the style of table 1 except the entry no, 3 whose first line is the Q bound e for this selected case, * 21 APPENDIX B Upper Bounds on Word Error Probability The word error probability P is rather tedious to compute for most codes; however, P may be easily bounded in a number of dif- e ferent ways. In this appendix we derive two upper bounds on P that are valid e for the binary symmetric channel (BSC), and call them P and Q . e e These bounds are functions of the binary error probability in the BSC. One is advised to use the least of the two bounds. P ^ min f P , Q ^ . (B-l) e V e e / The newer "union bound" P and the familiar "minimum distance e bound" Q are given next: e The Union Bound N m iM.m N-0 , p^ ^ = V M(i)p5'(i-p J ^ P^= )^ M(i)p-(l-p^) -I ^id ^l-p^' i=l k = e (B-2) ^ki min(i, [Tj+k) / i^ ' \ J = liJ where p = BSC error probability, N = code word or block length, M(i) = number of neighbors a distance i away from a given code word, [x]= integer part of ^(x + 1). 23 The Minimtirn Distance Bound - 1 d oi NA n,, .N-n Qe = ^ - I VnJPe ^^'^J ' (B-3) where n= o d - mininnum distance between code words, o Proof of the Union Bound Consider a code (i. e. , a finite set of code words) w , w,, . . . , w, , - all of length N. Assume that the distance structure o 1 M * of this block code is known, and let these known distances be d = d(w , w ), m = 1, . . . , M . (B-4) mom In this way we also know the neighbor counts that are exactly a distance i from w . Denote this count of i -neighbors by M(i), 1 ^ i ^ N. M M(i)= y 6i^d ' ^^-^^ m= 1 where 6. .is the Kronecker delta symibol, and 1. J N M(i) = M . (B-6) I i =1 As is customary, let w be the N bit error word, and let e be e the number of errors (number of ones) in w . Clearly, ^ e ^ N with e the smaller e values much more likely in practice. If a word w is sent, then w + w is received. Decoding errors o o e will occur whenever for some m(na = 1, . . . , M) w is as close or closer m 24 to w + w than w is. We denote the probability of this o to m error o e o event bv P . If a set of e errors contributes toward altering w em o into w , then each binary error must fall into one of two categories, m Take an error that occurs in a bit where w and w agree. Clearly, o m this error must move w one unit away from w . We denote the num- o rn ber of such (moving away) errors by e(*-m). An error in a digit where w and w differ must bring w one step toward w . We denote the o m o m number of errors in this second category (moving together) by e(— ^m). Immediately e(— m) + e(— m) = (B-7) a fact that is useful in bounding P em P ^ Prd(w + w , w ) ^ d(w + w , w ) em I o em o e o ^ P d + e(*-m) - e(-* m) ^ e m ^ P 2e(— m) s d m (B-8) ^ P e(— m) ^ N y P[e = n]. P[e(— m) s [dH I e = n] . n = m Both probabilities in the sum (B-8) are well known for BSC; thus, the P[ e = n] term is a mere binomial. N-i or 1 N ] n ,, iN-n ^Le = n] = [^) p (1 - p ) (B-9) 25 while the P[ . . . | e = n] term can be interpreted as a random population problenn (Feller, I960). Let a population of N elements consist of d red and N - d black elements. A group of n elements is chosen at mm randonn. We seek the probability that exactly j elements turn out to be red and n-j black. The well known answer is given by the hypergeometric distribution: (:-)(:» P[e(^m) = j |e = n] = ^-i-^;^^i^^^^L^ . (B-10) A substitution of (B-9) and (B-10) into (B-8) yields a bound on P , em It remains to take into account all code words m = 1, . . . , M. The overall word error probability P must surely be upper bounded by the "union bound" (Feller, I960, calls it the Boole's Inequality): M I m = 1 (B-12) N ^ V M(i) P / em i = l d =i A substitution of (B-11) into (B-12) plus a few housekeeping tasks, such as dubbing a combinational coefficient A and naming the entire right side P finally yields (B-2). p ^ V p e /. em 26 Proof of the Minimum Distance Bound Equation (B-3) is well known and obvious; therefore the following is given only for sake of completeness. Define the minimum distance d of a linear block code as o d = min d m 1 ^ m ^ M (B-13) and a quantity Q = P[ 2e ^ d ] e o (B-14) Then for any e, 1 = P[ 2e < d ] + P[2e ^ d ] o o ^ 1 - P + Q e e and, necessarily, P ^ Q ; while e e (3-15) Q = 1 - P[e < (d ] e I ol {B.16) can be expressed with the aid of (B-9). Note The "union bound" (B-2) becomes poor whenever the underlying events have large intersections in common. In our case, this is guaran- teed to occur for large p , say for lO"-*- ^ p ^ i. In such cases, P e e 2 e may even exceed unity --an altogether deplorable situation. But, then is the time to use the "nainimuna distance bound"(B-3), which is &.lways less than one. In the other extreme, when p is negligibly snnall < p << 1, P < Q and the "union bound" is the tightest of these two upper bounds. 27 GPO 830 - 057 PENN STATE UNIVERSITY LIBRARIES liiiillllilillillili ADDDD72D2D1DM