Coding Theory and Cryptography

Posted on 2021/10/11 by wdjoyner

This was once posted on my USNA webpage. Since I’ve retired, I’m going to repost it here.

Coding Theory and Cryptography:
From Enigma and Geheimschreiber to Quantum Theory
(David Joyner, ed.) Springer-Verlag, 2000.
ISBN 3-540-66336-3

Summary: These are the proceedings of the “Cryptoday” Conference on Coding Theory, Cryptography, and Number Theory held at the U. S. Naval Academy during October 25-26, 1998. This book concerns elementary and advanced aspects of coding theory and cryptography. The coding theory contributions deal mostly with algebraic coding theory. Some of these papers are expository, whereas others are the result of original research. The emphasis is on geometric Goppa codes, but there is also a paper on codes arising from combinatorial constructions. There are both, historical and mathematical papers on cryptography.
Several of the contributions on cryptography describe the work done by the British and their allies during World War II to crack the German and Japanese ciphers. Some mathematical aspects of the Enigma rotor machine and more recent research on quantum cryptography are described. Moreover, there are two papers concerned with the RSA cryptosystem and related number-theoretic issues.

Chapters

Reminiscences and Reflections of a Codebreaker, by Peter Hilton pdf
FISH and I, by W. T. Tutte pdf
Sturgeon, The FISH BP Never Really Caught, by Frode Weierud, pdf
ENIGMA and PURPLE: How the Allies Broke German and Japanese Codes During the War, by David A. Hatch pdf
The Geheimschreiber Secret, by Lars Ulfving, Frode Weierud pdf
The RSA Public Key Cryptosystem, by William P. Wardlaw pdf
Number Theory and Cryptography (using Maple), by John Cosgrave pdf
A Talk on Quantum Cryptography or How Alice Outwits Eve, by Samuel J. Lomonaco, Jr. pdf
The Rigidity Theorems of Hamada and Ohmori, Revisited, by T. S. Michael pdf
Counting Prime Divisors on Elliptic Curves and Multiplication in Finite Fields, by M. Amin Shokrollahi pdf,
On Cyclic MDS-Codes, by M. Amin Shokrollahi pdf
Computing Roots of Polynomials over Function Fields of Curves, by Shuhong Gao, M. Amin Shokrollahi pdf
Remarks on codes from modular curves: MAPLE applications, by David Joyner and Salahoddin Shokranian, pdf

For more cryptologic history, see the National Cryptologic Museum.

This is now out of print and will not be reprinted (as far as I know). The above pdf files are posted by written permission. I thank Springer-Verlag for this.

Duursma zeta function of a graph

Posted on 2020/05/28 by wdjoyner

I’m going to start off with two big caveats:

This is not Duursma‘s definition, it’s mine.
I’m not convinced (yet?) that it’s a useful idea to examine such a zeta function.

So that’s your warning – you may be wasting your time reading this!

The Duursma zeta function of a linear block (error-correcting) code is due to Iwan Duursma and is a fascinating object of study. (More precisely, it’s defined for “formal” linear block codes, ie, defined via a weight enumerator polynomial with a suitable MacWilliams-like functional equation.) Sometimes it satisfies an analog of the Riemann hypothesis and sometimes it doesn’t. And sometimes that analog is still an open question.

Duursma zeta function of a code

Before we define the Duursma zeta function of a graph, we introduce the Duursma zeta function of a code.

Let $C$ be an $[n,k,d]_q$ code, ie a linear code over $GF(q)$ of length $n$ , dimension $k$ , and minimum distance $d$ . In general, if $C$ is an $[n,k,d]_q$ -code then we use $[n,k^\perp,d^\perp]_q$ for the parameters of the dual code, $C^\perp$ . It is a consequence of Singleton’s bound that $n+2-d-d^\perp\geq$ , with equality when $C$ is an MDS code. Motivated by analogies with local class field theory, in [Du] Iwan Duursma introduced the (Duursma) zeta function $\zeta=\zeta_C$ :

$\zeta_C(T)=\frac{P(T)}{(1-T)(1-qT)},$
where $P(T)=P_C(T)$ is a polynomial of degree $n+2-d-d^\perp$ , called the zeta polynomial of $C$ . We next sketch the definition of the zeta polynomial.

If $C^\perp$ denotes the dual code of $C$ , with parameters $[n,n-k,d^\perp]$ then the MacWilliams identity relates the weight enumerator $A_{C^\perp}$ of $C^\perp$ to the weight enumerator $A_{C}$ of $C$ :

$A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y).$
A polynomial $P(T)=P_C(T)$ for which

$\frac{(xT+(1-T)y)^n}{(1-T)(1-qT)}P(T)=\dots +\frac{A_C(x,y)-x^n}{q-1}T^{n-d}+\dots \ .$
is a (Duursma) zeta polynomial of $C$ .

Theorem (Duursma): If $C$ be an $[n,k,d]_q$ code with $d\geq 2$ and $d^\perp\geq 2$ then the Duursma zeta polynomial $P=P_C$ exists and is unique.

See the papers of Duursma for interesting properties and conjectures.

Duursma zeta function of a graph

Let $\Gamma=(V,E)$ be a graph having $|V(\Gamma)|$ vertices and $|E(\Gamma)|$ edges. We define the zeta function of $\Gamma$ via the Duursma zeta function of the binary linear code defined by the cycle space of $\Gamma$ .

Theorem (see [DKR], [HB], [JV]): The binary code $B=B_\Gamma$ generated by the rows of the incidence matrix of $\Gamma$ is the cocycle space of $\Gamma$ over $GF(2)$ , and the dual code $B^\perp$ is the cycle space $Z=Z_\Gamma$ of $\Gamma$ :

$B_\Gamma^\perp = Z_\Gamma.$
Moreover,
(a) the length of $B_\Gamma$ is $|E|$ , dimension of $B_\Gamma$ is $|V|-1$ , and the minimum distance of $B_\Gamma$ is the edge-connectivity of $\Gamma$ ,
(b) length of $Z_\Gamma$ is $|E|$ , dimension of $Z_\Gamma$ is $|E|-|V|+1$ , and the minimum distance of $Z_\Gamma$ is the girth of $\Gamma$ .

Call $Z_\Gamma$ the cycle code and $B_\Gamma$ the cocycle code.

Finally, we can introduce the (Duursma) zeta function $\Gamma$ :

$\zeta_\Gamma(T)=\zeta_{Z_\Gamma} =\frac{P(T)}{(1-T)(1-qT)},$
where $P=P_\Gamma=P_{Z_\Gamma}$ is the Duursma polynomial of $\Gamma$ .

Example: Using SageMath, when $\Gamma = W_5$ , the wheel graph on 5 vertices, we have

$P_\Gamma(T) = \frac{2}{7}T^4 + \frac{2}{7}T^3 + \frac{3}{14}T^2 + \frac{1}{7}T + \frac{1}{14}.$
All its zeros are of absolute value $1/\sqrt{2}$ .

References

[Du] I. Duursma, Combinatorics of the two-variable zeta function, in Finite fields and applications, 109–136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.

[DKR] P. Dankelmann, J. Key, B. Rodrigues, Codes from incidence matrices of graphs, Designs, Codes and Cryptography 68 (2013) 373-393.

[HB] S. Hakimi and J. Bredeson, Graph theoretic error-correcting codes, IEEE Trans. Info. Theory 14(1968)584-591.

[JV] D. Jungnickel and S. Vanstone, Graphical codes revisited, IEEE Trans. Info. Theory 43(1997)136-146.

Ring theory, via coding theory and cryptography

Posted on 2018/04/01 by wdjoyner

In these notes on ring theory, I tried to cover enough material to get a feeling for basic ring theory, via cyclic codes and ring-based cryptosystems such as NTRU. Here’s a list of the topics.

1 Introduction to rings
1.1 Definition of a ring
1.2 Integral domains and fields
1.3 Ring homomorphisms and ideals
1.4 Quotient rings
1.5 UFDs
1.6 Polynomial rings
1.6.1 Application: Shamir’s Secret Sharing Scheme
1.6.2 Application: NTRU
1.6.3 Application: Modified NTRU
1.6.4 Application to LFSRs

2 Structure of finite fields
2.1 Cyclic multiplicative group
2.2 Extension fields
2.3 Back to the LFSR

3 Error-correcting codes
3.1 The communication model
3.2 Basic definitions
3.3 Binary Hamming codes
3.4 Coset leaders and the covering radius
3.5 Reed-Solomon codes as polynomial codes
3.6 Cyclic codes as polynomial codes
3.6.1 Reed-Solomon codes as cyclic codes
3.6.2 Quadratic residue codes
3.6.3 BCH bound for cyclic codes
3.6.4 Decoding cyclic codes
3.6.5 Cyclic codes and LFSRs

4 Lattices
4.1 Basic definitions
4.2 The shortest vector problem
4.2.1 Application to a congruential PKC
4.3 LLL and a reduced lattice basis
4.4 Hermite normal form
4.5 NTRU as a lattice cryptosystem

A tribute to TS Michael

Posted on 2016/11/30 by wdjoyner

I’ve known TS for over 20 years as a principled colleague and a great teacher.

TS at the USNA in Dec 2015.

However, we really never spoke much except for the past five-to-ten years or so. For a period, I wrote a lot about error-correcting codes and we’d talk occasionally about our common interests (for example, I found his paper “The rigidity theorems of Hamada and Ohmori, revisited” fascinating). However, once I became interested in graph theory, we spoke as often as I could corner him. He taught me a lot and only know I realize how lucky I was to have him as a colleague.

I remember many times, late on a Friday, when we’d talk for an hour or two about chess, mathematics, “office politics” (he always knew more than me), and allergies. Here’s one of his favorite chess problems:

Mate in 549 moves. This problem was discovered by a team of chess engame experts at Lomonosov University, Moscow, August 2012.

Maybe this says more about me than him, but when it was just the two of us, we rarely talked about families or relationships. None-the-less, he always treated me like a good friend. One of my favorite memories was when my wife and I were shopping at the plaza where his condo building was located (it’s a big plaza). Elva and I were walking store-to-store when we spotted TS. He was walking to distract himself from his discomfort. At the time, doctors didn’t know what his problems were and he suspected allergies. I have a number of food sensitivities and he was a welcomed fountain of medical knowledge about these issues. (In fact, his hints have really helped me a lot, health-wise.) In any case, TS and Elva and I spoke for 30 minutes or so about health and family. I remember how gracious and thoughtful he was, skillfully steering the conversation into non-technical matters for Elva’s benefit. I ran into him another time while waiting for Elva, who was in a nearby doctor’s office (I told you this was a big shopping plaza). TS generously waited with me until Elva was ready to be picked up. What we chatted about is lost in the cobwebs of my memory but I remember vividly where we sat and the kind of day it was. TS had such a kind heart.

As I said, TS taught me a lot about graph theory. Whether in-between classes or when I was lucky enough to spot him late in the day, he’d kindly entertain my naive (usually false) conjectures and speculations about strongly regular graphs. I never heard him speak in anything but the kindest terms. He’d never say “that’s just plain wrong” or “idiotic” (even if it was) but instead teach me the correct way to think about it in a matter in which I could see myself how my speculations were wrong-headed. My upcoming book with Caroline Melles is indebted to his insight and suggestions.

Even after he left Maryland to spend his remaining days with his family in California, TS emailed encouragement and suggestions about an expository paper I was writing to help connect my matrix theory students with the methods of ranking sports teams. While he was very helpful and provided me with his excellent insights as usual, in truth, I used the work on the paper as an excuse to keep up with his health status. I’m relatively ignorant of medical issues and tried to stay optimistic until it’s totally unrealistic. As sad as it was, we was always frank and honest with me about his prognosis.

He’s gone now, but as a teacher, researcher, and as a kind soul, TS is unforgettable.

A list of TS’s publications:

T. S. Michael, Tournaments, book chapter in Handbook of Linear Algebra, 2nd ed, CRC Press, Boca Raton, 2013.
T. S. Michael, Cycles of length 5 in triangle-free graphs: a sporadic counterexample to a characterization of equality, Bulletin of the Institute of Combinatorics and Its Applications, 67 (2013) 6–8.
T. S. Michael and Val Pinciu, Guarding orthogonal prison yards: an upper bound,
Congressus Numerantium, 211 (2012) 57–64.
Ilhan Hacioglu and T. S. Michael, The p-ranks of residual and derived skew Hadamard designs,
Discrete Mathematics, 311 (2011) 2216-2219.
T. S. Michael, Guards, galleries, fortresses, and the octoplex, College Math Journal, 42 (2011) 191-200. (This paper won a Polya Award)
Elizabeth Doering, T. S. Michael, and Bryan Shader, Even and odd tournament matrices with minimum rank over finite fields, Electronic Journal of Linear Algebra, 22 (2011) 363-377.
Brenda Johnson, Mark E. Kidwell, and T. S. Michael, Intrinsically knotted graphs have at least 21 edges, Journal of Knot Theory and Its Ramifications, 19 (2010) 1423-1429.
T. S. Michael, How to Guard an Art Gallery and Other Discrete Mathematical Adventures. Johns Hopkins University Press, Baltimore, 2009.
T. S. Michael and Val Pinciu, Art gallery theorems and triangulations, DIMACS Educational Module Series, 2007, 18 pp (electronic 07-1)
T. S. Michael and Thomas Quint, Sphericity, cubicity, and edge clique covers of graphs, Discrete Applied Mathematics, 154 (2006) 1309-1313.
T. S. Michael and Val Pinciu, Guarding the guards in art galleries, Math Horizons, 14 (2006), 22-23, 25.
Richard J. Bower and T. S. Michael, Packing boxes with bricks, Mathematics Magazine, 79 (2006), 14-30.
T. S. Michael and Thomas Quint, Optimal strategies for node selection games: skew matrices and symmetric games, Linear Algebra and Its Applications 412 (2006) 77-92.
T. S. Michael, Ryser’s embedding problem for Hadamard matrices, Journal of Combinatorial Designs 14 (2006) 41-51.
Richard J. Bower and T. S. Michael, When can you tile a box with translates of two given rectangular bricks?, Electronic Journal of Combinatorics 11 (2004) Note 7, 9 pages.
T. S. Michael and Val Pinciu, Art gallery theorems for guarded guards, Computational Geometry 26 (2003) 247-258.
T. S. Michael, Impossible decompositions of complete graphs into three Petersen subgraphs, Bulletin of the Institute of Combinatorics and Its Applications 39 (2003) 64-66.
T. S. Michael and William N. Traves, Independence sequences of well-covered graphs: non-unimodality and the roller-coaster conjecture, Graphs and Combinatorics 19 (2003) 403-411.
T. S. Michael and Thomas Quint, Sphere of influence graphs and the L-Infinity metric, Discrete Applied Mathematics 127 (2003) 447-460.
T. S. Michael, Signed degree sequences and multigraphs, Journal of Graph Theory 41 (2002) 101-105.
T. S. Michael and Val Pinciu, Multiply guarded guards in orthogonal art galleries, Lecture Notes in Computer Science 2073, pp 753-762, in: Proceedings of the International Conference on Computer Science, San Francisco, Springer, 2001.
T. S. Michael, The rigidity theorems of Hamada and Ohmori, revisited, in Coding Theory and Cryptography: From the Geheimschreiber and Enigma to Quantum Theory. (Annapolis, MD, 1998), 175-179, Springer, Berlin, 2000.
T. S. Michael and Thomas Quint, Sphere of influence graphs in general metric spaces, Mathematical and Computer Modelling, 29 (1999) 45-53.
Suk-Geun Hwang, Arnold R. Kraeuter, and T. S. Michael, An upper bound for the permanent of a nonnegative matrix, Linear Algebra and Its Applications 281 (1998), 259-263.
* First Corrections: Linear Algebra and Its Applications 300 (1999), no. 1-3, 1-2
T. S. Michael and W. D. Wallis, Skew-Hadamard matrices and the Smith normal form, Designs, Codes, and Cryptography, 13 (1998) 173-176.
T. S. Michael, The p-ranks of skew Hadamard designs, Journal of Combinatorial Theory, Series A, 73 (1996) 170-171.
T. S. Michael, The ranks of tournament matrices, American Mathematical Monthly, 102 (1995) 637-639.
T. S. Michael, Lower bounds for graph domination by degrees, pp 789-800 in Graph Theory, Combinatorics, and Algorithms: Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Y. Alavi and A. Schwenk (eds.), Wiley, New York, 1995.
T. S. Michael and Thomas Quint, Sphere of influence graphs: a survey, Congressus Numerantium, 105 (1994) 153-160.
T. S. Michael and Thomas Quint, Sphere of influence graphs: edge density and clique size, Mathematical and Computer Modelling, 20 (1994) 19-24.
T. S. Michael and Aaron Stucker, Mathematical pitfalls with equivalence classes, PRIMUS, 3 (1993) 331-335.
T. S. Michael, The structure matrix of the class of r-multigraphs with a prescribed degree sequence, Linear Algebra and Its Applications, 183 (1993) 155-177.
T. S. Michael, The decomposition of the complete graph into three isomorphic strongly regular graphs, Congressus Numerantium, 85 (1991) 177-183.
T. S. Michael, The structure matrix and a generalization of Ryser’s maximum term rank formula, Linear Algebra and Its Applications, 145 (1991) 21-31.
Richard A. Brualdi and T. S. Michael, The class of matrices of zeros, ones and twos with prescribed row and column sums, Linear Algebra and Its Applications, 114(115) (1989) 181-198.
Richard A. Brualdi and T. S. Michael, The class of 2-multigraphs with a prescribed degree sequence, Linear and Multilinear Algebra, 24 (1989) 81-102.
Richard A. Brualdi, John L. Goldwasser, and T. S. Michael, Maximum permanents of matrices of zeros and ones, Journal of Combinatorial Theory, Series A, 47 (1988) 207-245.

Real world applications of representation theory

Posted on 2016/08/06 by wdjoyner

(Subtitle: Representation theorists will rule the world one day just you wait)

This post describes some applications of representation theory of non-abelian groups to various fields and gives some references.

Engineering.
- Tensegrity – the design of “strut-and-cable” constructions.Want to build a building with cables and struts but don’t know representation theory? Check out these references:
  - R. Connelly and A. Back, “Mathematics and tensegrity”, Amer Scientist, April-May 1998, pages 142-151
  - symmetric tensegrities
- Telephone network designs.This is the information age with more and more telephone lines needed every day. Want to reach out and touch someone? You need representation theory.
  - F. Bien, “Construction of telephone networks by group representations”, Notices A. M. S. 36(1989)5-22
- Nonlinear network problems.This is cheating a little since the works in the reference below really use the theory of Lie groups instead of representation theory itself. Still, there is a tangential relation at least between representation theory of Lie groups and the solution to certain nonlinear network problems.
  - C. Desoer, R. Brockett, J. Wood, R. Hirshorn,
    A. Willsky, G. Blankenship, Applications of Lie group theory to nonlinear network problems, (Supplement to IEEE Symposium on Circuit Theory, 1974), Western Periodicals Co., N. Hollywood, CA, 1974
- Control theory.
  - R. W. Brockett, “Lie theory and control systems defined on spheres”, SIAM J on Applied Math 25(1973) 213-225
- Robotics.The future is not in plastics (see the movie “The Graduate“) but in robotics.
  How do you figure out their movements before building them? You guessed it, using representation theory.
  - G. Chirikjian, “Determination and synthesis of discretely actuated manipulator workspaces using harmonic analysis”, in Advances in Robotic Kinematics, 5, 1996, Springer-Verlag
  - G. Chirikjian and I. Ebert-Uphoff, “Discretely actuated manipulator workspace generation by closed-form convolution”, in ASME Design Engineering Technical Conference, August 18-22 1996
- Radar design.W. Schempp, Harmonic analysis on the Heisenberg nilpotent Lie group, with
  applications to signal theory, Longman Scientific & Technical, New York (Copublished in the U.S. with Wiley), 1986.
- Antenna design.B. Hassibi, B. Hochwald, A. Shokrollahi, W. Sweldens, “Representation theory for high-rate multiple antenna code design,” 2000 preprint (see A. Shokrollahi’s site for similar works).
- Design of stereo systems.We’re talkin’ quadrophonic state-of-the-art.
  - K. Hannabus, “Sound and symmetry”, Math. Intelligencer, 19, Fall 1997, pages 16-20
- Coding theory. Interesting progress in coding theory has been made using group theory and representation theory. Here are a few selected references.
  - F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes,
    North-Holland/Elsevier, 1993 (8th printing)
  - I. Blake and R. Mullin, Mathematical Theory of Coding, Academic Press, 1975
    49(1995)215-223
  - J.-P. Tillich and G. Zemor,
    “Optimal cycle codes constructed from Ramanujan graphs,” SIAM J on Disc. Math. 10(1997)447-459
  - H. Ward and J. Wood, “Characters and the equivalence of codes,” J. Combin. Theory A 73348-352
  - J. Lafferty and D. Rockmore, “Spectral Techniques for Expander Codes” , (Extended Abstract) 1997 Symposium on Theory of Computation (available
    at Dan Rockmore’s web page)
Mathematical physics.
Any complete list of books and papers in this field which use representation theory would be much too long for the limited goal we have here (which is simply
to list some real-world applications). A small selection is given below.
- Differential equations (such as the heat equation, Schrodinger wave equation, etc).M. Craddock, “The symmetry groups of linear partial differential equations
  and representation theory, I” J. Diff. Equations 116(1995)202-247
- Mechanics.
  - D.H. Sattinger, O.L. Weaver, Lie Groups and Algebras With Applications to Physics, Geometry, and Mechanics (Applied Mathematical Sciences, Vol 61) , Springer Verlag, 1986
  - Johan Belinfante, “Lie algebras and inhomogeneous simple materials”,
    SIAM J on Applied Math 25(1973)260-268
- Models for elementary particles.
  - Howard Georgi, Lie Algebras in Particle Physics, Addison-Wesley, 1995
  - J. Baez, “This week’s finds in mathematical physics – week 119,” posted to sci.math.research on 4-13-1998
- Quantum mechanics.
  - Eugene Wigner, “Reduction of direct products and restriction of representations to subgroups: the everyday tasks of the quantum theorists”, SIAM J on Applied Math 25(1973) 169-185
  - V. Vladimirov, I. Volovich, and E. Zelenov, “Spectral theory in p-adic quantum mechanics and representation theory,” Soviet Math. Doklady 41(1990)40-44
- p-adic string theory.
  - Y. Manin, “Reflections on arithmetical physics,” in Conformal invariance and string theory, Academic Press, 1989, pages 293-303
  - V. Vladimirov, I. Volovich, and E. Zelenov, p-adic analysis and mathematical physics, World Scientific, 1994
  - V. Vladimirov, “On the Freund-Witten adelic formula for Veneziano amplitudes,” Letters in Math. Physics 27(1993)123-131
Mathematical chemistry.
- Spectroscopy.B. Judd, “Lie groups in Atomic and molecular spectroscopy”, SIAM J on Applied Math 25(1973) 186-192
- Crystallography.
  - G. Ramachandran and R. Srinivasan, Fourier methods in crystallography,
    New York, Wiley-Interscience, 1970.
  - T. Janssen, Crystallographic groups, North-Holland Pub., London, 1973.
  - J. Zak, A. Casher, M. Gluck, Y. Gur, The irreducible representations of space groups, W. A. Benjamin, Inc., New York, 1969.
- Molecular strucure of the Buckyball.
  - F. Chung and S. Sternberg, “Mathematics and the buckyball”, American Scientist 83(1993)56-71
  - F. Chung, B. Kostant, and S. Sternberg, “Groups and the buckyball”, in Lie theory and geometry, (ed. J.-L. Brylinski et al), Birkhauser, 1994
  - G. James, “The representation theory for the Buckminsterfullerene,” J. Alg. 167(1994)803-820
Knot theory (which, in turn, has applications to modeling DNA) uses representation theory. F. Constantinescu and F. Toppan, “On the linearized Artin braid representation,” J. Knot Theory and its Ramifications, 2(1993)
The Riemann hypothesis.
Think you’re going to solve the Riemann hypothesis without using
representation theory? Check this paper out: A. Connes, “Formule de traces en geometrie non-commutative et hypothese de Riemann”, C. R. Acad. Sci. Paris 323 (1996)1231-1236. (For those who argue that this is not a real-world application, we refer to Barry Cipra’s article, “Prime Formula Weds Number Theory and Quantum Physics,” Science, 1996 December 20, 274, no. 5295, page 2014, in Research News.)
Circuit design, statistics, signal processing, …
See the survey paper
D. Rockmore, “Some applications of generalized FFTs” in Proceedings of the DIMACS
Workshop on Groups and Computation, June 7-10, 1995 eds. L. Finkelstein and W. Kantor, (1997) 329–369. (available at Dan Rockmore’s web page)
Vision – See the survey papers by Jacek Turski:Geometric Fourier Analysis of the Conformal Camera for Active Vision, SIAM Review, Volume 46 Issue 2 pages 230-255, 2004 Society for Industrial and Applied Mathematics, and, Geometric Fourier Analysis for Computational Vision, JFAA 11, 1-23, 2005.

Hill verses Hamming

Posted on 2016/08/05 by wdjoyner

It’s easy to imagine the 19th century Philadelphia wool dealer Frank J. Primrose as a happy man. I envision him shearing sheep during the day, while in the evening he brings his wife flowers and plays games with his little children until bedtime. However, in 1887 Frank J. Primrose was not a happy man. This is because in June of that year, he had telegraphed his agent in Kansas instructions to buy a certain amount of wool. However, the telegraph operator made a single mistake in transmitting his message and Primrose unintentionally bought far more wool than he could possibly sell. Ordinarily, such a small error has little consequence, because errors can often be detected from the context of the message. However, this was an unusual case and the mistake cost him about a half-million dollars in today’s money. He promptly sued and his case eventually made its way to the Supreme Court. The famous 1894 United States Supreme Court case Primrose v. Western Union Telegraph Company decided that the telegraph company was not liable for the error in transmission of a message.

Thus was born the need for error-correcting codes.

Introduction

Lester Hill is most famously known for the Hill cipher, frequently taught in linear algebra courses today. We describe this cryptosystem in more detail in one of the sections below, but here is the rough idea. In this system, developed and published in the 1920’s, we take a $k\times k$ matrix K, composed of integers between 0 and 25, and encipher plaintext p by $p\longmapsto c=Kp$ , where the arithmetical operations are performed mod 26. Here K is the key, which should be known only to the sender and the intended receiver, and c is the ciphertext transmitted to the receiver.

On the other hand, Richard Hamming is known for the Hamming codes, also frequently taught in a linear algebra course. This will be describes in more detail in one of the sections below, be here is the basic idea. In this scheme, developed in the 1940’s, we take a $k\times k$ matrix G over a finite field F, constructed in a very particular way, and encode a message m by $m\longmapsto c=mG$ , where the arithmetical operations are performed in F. The matrix G is called the generator matrix and c is the codeword transmitted to the receiver.

Here, in a nutshell, is the mystery at the heart of this post.

These schemes of Hill and Hamming, while algebraically very similar, have quite different aims. One is intended for secure communication, the other for reliable communication. However, in an unpublished paper [H5], Hill developed a hybrid encryption/error-detection scheme, what we shall call “Hill codes” (described in more detail below).

Why wasn’t Hill’s result published and therefore Hill, more than Hamming, known as a pioneer of error-correcting codes?

Perhaps Hill himself hinted at the answer. In an overly optimistic statement, Hill wrote (italics mine):

Further problems connected with checking operations in finite fields will be treated in another paper. Machines may be devised to render almost quite automatic the evaluation of checking elements $c_1,\dots,c_q$ according to any proposed reference matrix of the general type described in Section 7, whatever the finite field in which the operations are effected. Such machines would enable us to dispense entirely with tables of any sort, and checks could be determined with great speed. But before checking machines could be seriously planned, the following problem — which is one, incidentally, of considerable interest from the standpoint of pure number theory — would require solution.

– Lester Hill, [H5]

By my interpretation, this suggests Hill wanted to answer the question below before moving on. As simple looking as it is, this problem is still, as far as I know, unsolved at the time of this writing.

Question 1 (Hill’s Problem):
Given k and q, find the largest r such that there exists a $k\times r$ van der Monde matrix with the property that every square submatrix is non-singular.

Indeed, this is closely related to the following related question from MacWilliams-Sloane [MS77], also still unsolved at this time. (Since Cauchy matrices do give a large family of matrices with the desired property, I’m guessing Hill was not aware of them.)

Question 2: Research Problem (11.1d)
Given k and q, find the largest r such that there exists a $k\times r$ matrix having entries in GF(q) with the property that every square submatrix is non-singular.

In this post, after brief biographies, an even more brief description of the Hill cipher and Hamming codes is given, with examples. Finally, we reference previous blog posts where the above-mentioned unpublished paper, in which Hill discovered error-correcting codes, is discussed in more detail.

Short biographies

Who is Hill? Recent short biographies have been published by C. Christensen and his co-authors. Modified slightly from [C14] and [CJT12] is the following information.

Lester Sanders Hill was born on January 19, 1890 in New York. He graduated from Columbia University in 1911 with a B. A. in Mathematics and earned his Master’s Degree in 1913. He taught mathematics for a few years at Montana University, then at Princeton University. He served in the United States Navy Reserves during World War I. After the WWI, he taught at the University of Maine and then at Yale, from which he earned his Ph.D. in mathematics in 1926. His Ph.D. advisor is not definitely known at this writing but I think a reasonable guess is Wallace Alvin Wilson.

In 1927, he accepted a position with the faculty of Hunter College in New York City, and he remained there, with one exception, until his resignation in 1960 due to illness. The one exception was for teaching at the G.I. University in Biarritz in 1946, during which time he may have been reactivated as a Naval Reserves officer. Hill died January 9, 1961.

Thanks to an interview that David Kahn had with Hill’s widow reported in [C14], we know that Hill loved to read detective stories, to tell jokes and, while not shy, enjoyed small gatherings as opposed to large parties.

Who is Hamming? His life is much better known and details can be readily found in several sources.

Richard Wesley Hamming was born on February 11, 1915, in Chicago. Hamming earned a B.S. in mathematics from the University of Chicago in 1937, a masters from the University of Nebraska in 1939, and a PhD in mathematics (with a thesis on differential equations)
from the University of Illinois at Urbana-Champaign in 1942. In April 1945 he joined the Manhattan Project at the Los Alamos Laboratory, then left to join the Bell Telephone Laboratories in 1946. In 1976, he retired from Bell Labs and moved to the Naval Postgraduate School in Monterey, California, where he worked as an Adjunct Professor
and senior lecturer in computer science until his death on January 7, 1998.

Hill’s cipher

The Hill cipher is a polygraphic cipher invented by Lester S. Hill in 1920’s. Hill and his colleague Wisner from Hunter College filed a patent for a telegraphic device encryption and error-detection device which was roughly based on ideas arising from the Hill cipher. It appears nothing concrete became of their efforts to market the device to the military, banks or the telegraph company (see Christensen, Joyner and Torres [CJT12] for more details). Incidently, Standage’s excellent book [St98] tells the amusing story of the telegraph company’s failed attempt to add a relatively simplistic error-detection to telegraph codes during that time period.

Some books state that the Hill cipher never saw any practical use in the real world. However, research by historians F. L. Bauer and David Kahn uncovered the fact that the Hill cipher saw some use during World War II encrypting three-letter groups of radio call signs [C14]. Perhaps insignificant, at least compared to the practical value of Hamming codes, none-the-less, it was a real-world use.

The following discussion assumes an elementary knowledge of matrices. First, each letter is first encoded as a number, namely

$A \leftrightarrow 0, B \leftrightarrow 1, \dots, Z \leftrightarrow 25$ . The subset of the integers $\{0, 1, \dots , 25\}$ will be denoted by Z/26Z. This is closed under addition and multiplication (mod 26), and sums and products (mod 26) satisfy the usual associative and distributive properties. For R = Z/26Z, let GL(k,R) denote the set of invertible matrix transformations $T:R^k\to R^k$ (that is, one-to-one and onto linear functions).

The construction

Suppose your message m consists of n capital letters, with no spaces. This may be regarded an n-tuple M with elements in R = Z/26Z. Identify the message M as a sequence of column vectors ${\bf p}\in R^k$ . A key in the Hill cipher is a $k\times k$ matrix K, all of whose entries are in R, such that the matrix K is invertible. It is important to keep K and k secret.

The encryption is performed by computing ${\bf c} = K{\bf p},$ and rewriting the resulting vector as a string over the same alphabet. Decryption is performed similarly by computing ${\bf p} = K^{-1} {\bf c}.$ .

Example 1: Suppose m is the message “BWGN”. Transcoding into numbers, the plaintext is rewritten $p_0=1, p_1=22, p_2=6, p_3=13$ . Suppose the key is
$K=\left(\begin{array}{rr} 1 & 3 \\ 5 & 12 \end{array}\right).$
Using Hill’s encryption above gives $c_0=7,c_1=3,c_2=24,c_3=3$ . (Verification is left to the reader as an exercise.)

Security concerns: For example, this cipher is linear and can be broken by a known plaintext attack.

Hamming codes

Richard Hamming is a pioneer of coding theory, introducing the binary
Hamming codes in the late 1940’s. In the days when an computer error could crash the computer and force the programmer to retype his punch cards, Hamming, out of frustration, designed a system whereby the computer could automatically correct certain errors. The family of codes named after him can easily correct one error.

Hill’s unpublished paper

While he was a student at Yale, Hill published three papers in Telegraph and Telephone Age [H1], [H2], [H3]. In these papers Hill described a mathematical method for checking the accuracy of telegraph communications. There is some overlap with these papers and [H5], so it seems likely to me that Hill’s unpublished paper [H5] dates from this time (that is, during his later years at Yale or early years at Hunter).

In [H5], Hill describes a family of linear block codes over a finite field and an algorithm for error-detection (which can be easily extended to error-correction). In it, he states the construction of what I’ll call the “Hill codes,” (defined below), gives numerous computational examples, and concludes by recording Hill’s Problem (stated above as Question 1). It is quite possibly Hill’s best work.

Here is how Hill describes his set-up.

Our problem is to provide convenient and practical accuracy checks upon
a sequence of n elements $f_1, f_2, \dots, f_r$ in a finite algebraic
field F. We send, in place of the simple sequence $f_1, f_2, \dots, f_r$ , the amplified sequence $f_1, f_2, \dots, f_r, c_1, c_2, \dots, c_k$
consisting of the “operand” sequence and the “checking” sequence.

– Lester Hill, [H5]

Then Hill continues as follows. Let F=GF(p) denote the finite field having p elements, where $p>2$ is a prime number. The checking sequence contains k elements of F as follows:
$c_j = \sum_{i=1}^r a_{i}^jf_i,$
for $j = 1, 2, \dots, k$ . The checks are to be determined by means of a
fixed matrix
$A = \left( \begin{array}{cccc} a_{1} & a_{2} & \dots & a_{r} \\ a_{1}^2 & a_{2}^2 & \dots & a_{r}^2 \\ \vdots & & & \vdots \\ a_{1}^k & a_{2}^k & \dots & a_{r}^k \\ \end{array} \right)$
of elements of F, the matrix having been constructed according to the criteria in Hill’s Problem above. In other words, if the operand sequence (i.e., the message) is the vector ${\bf f} = (f_1, f_2, \dots, f_r)$ , then the amplified sequence (or codeword in the Hill code) to be transmitted is

${\bf c} = {\bf f}G,$
where $G = \left( I_r, A \right)$ and where $I_r$ denotes the
$r\times r$ identity matrix. The Hill code is the row space of G.

We conclude with one more open question.

Question 3:
What is the minimum distance of a Hill code?

The minimum distance of any Hamming code is 3.

Do all sufficiently long Hill codes have minimum distance greater than 3?

Summary

Most books today (for example, the excellent MAA publication written by Thompson [T83]) date the origins of the theory of error-correcting codes to the late 1940s, due to Richard Hamming. However, this paper argues that the actual birth is in the 1920s due to Lester Hill. Topics discussed include why Hill’s discoveries weren’t publicly known until relatively recently, what Hill actually did that trumps Hamming, and some open (mathematical) questions connected with Hill’s work.

For more details, see these previous blog posts.

Acknowledgements: Many thanks to Chris Christensen and Alexander Barg for
helpful and encouraging conversations. I’d like to explicitly credit Chris Christensen, as well as historian David Kahn, for the original discoveries of the source material.

Bibliography

[C14] C. Christensen, Lester Hill revisited, Cryptologia 38(2014)293-332.

[CJT12] ——, D. Joyner and J. Torres, Lester Hill’s error-detecting codes, Cryptologia 36(2012)88-103.

[H1] L. Hill, A novel checking method for telegraphic sequences, Telegraph and
Telephone Age (October 1, 1926), 456 – 460.

[H2] ——, The role of prime numbers in the checking of telegraphic communications, I, Telegraph and Telephone Age (April 1, 1927), 151 – 154.

[H3] ——, The role of prime numbers in the checking of telegraphic
communications, II, Telegraph and Telephone Age (July, 16, 1927), 323 – 324.

[H4] ——, Lester S. Hill to Lloyd B. Wilson, November 21, 1925. Letter.

[H5] ——, Checking the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields, undated and unpublished notes, 40 pages.
(hill-error-checking-notes-unpublished)

[MS77] F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

[Sh] A. Shokrollahi, On cyclic MDS codes, in Coding Theory and Cryptography: From Enigma and Geheimschreiber to Quantum Theory, (ed. D. Joyner), Springer-Verlag, 2000.

[St98] T. Standage, The Victorian Internet, Walker & Company, 1998.

[T83] T. Thompson, From Error-Correcting Codes Through Sphere Packings to Simple Groups, Mathematical Association of America, 1983.

Lester Hill’s “The checking of the accuracy …” – finally completed

Posted on 2015/03/13 by wdjoyner

I’ve finally finished LaTeXing Lester Hill’s manuscript. You can download the pdf here: hill-error-checking-notes-unpublished. Just ask if you want a copy of the latex source.

This post is to simply state Hill’s conclusion. It gives a clue as to why the paper was never published. If I had to guess, I’d say it was because he could not solve the problem he stated in that section.

As far as I know it is still unsolved.

Here is Hill’s Conclusion section:

Further problems connected with checking operations in finite fields will be treated in another paper. Machines may be devised to render almost quite automatic the evaluation of checking elements $c_1,c_2,\dots,c_q$ according to any proposed reference matrix of the general type described in Section 7, whatever the finite field in which the operations are effected. Such machines would enable us to dispense entirely with tables of any sort, and checks could be determined with great speed. But before checking machines could be seriously planned, the following problem — which is one, incidentally, of considerable interest from the standpoint of pure number theory — would require solution:

To construct, for a given finite field $F$ with $\Gamma$ elements, and for the checking therein of $n$ -element sequence $f_1,f_2,\dots,f_n$ , a reference matrix

$\left( \begin{array}{cccc} a_1 & a_2 & \dots & a_{n} \\ a_1^2 & a_2^2 & \dots & a_{n}^2 \\ \vdots & & & \vdots \\ a_1^q & a_2^q & \dots & a_{n}^q \\ \end{array} \right)$

without a vanishing determinant of any order, in which the integer $q$ is the greatest possible. Corresponding to any $F$ , and any $n$ — provided that $n$ is less than $\Gamma$ — there is a definite maximum $q$ . This maximum should be ascertained, and the reference matrix therefore constructed.

We are not able to communicate a solution of this general problem.

(signed) Lester S. Hill

Lester Hill’s “The checking of the accuracy …”, part 14

Posted on 2015/02/26 by wdjoyner

Backstory: Lester Saunders Hill wrote unpublished notes, about 40 pages long, probably in the mid- to late 1920s. They were titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this manuscript was given to David Kahn by Hill’s widow. The notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. I thank Chris Christensen, the National Cryptologic Museum, and NSA’s David Kahn Collection, for their help in obtaining these notes. Many thanks also to Rene Stein of the NSA Cryptologic Museum library and David Kahn for permission to publish this transcription. Comments by transcriber will look like this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the 15th section of his paper. I hope to post more later. (Part 14 is here.)

Lemma concerning reference matrices

The general reference matrix of Section 3 was:

$Q = \left( \begin{array}{cccc} k_{11} & k_{12} & \dots & k_{1n} \\ k_{21} & k_{22} & \dots & k_{2n} \\ \vdots & & & \vdots \\ k_{q1} & k_{q2} & \dots & k_{qn} \\ \end{array} \right)$
the $k_{ij}$ being elements of any given finite algebraic field $F$ , and $q$ being less than or equal to $n$ .

This matrix contains determinants of order $r$ with $r=1,2,\dots, q$ — determinants of first order ( $r=1$ ) being single elements of the matrix.

We recall that if $f_1$ , $f_2, \dots, f_{s}$ is an $s$ element operand
sequence in $F$ , a $t$ -element check based upon the matrix $Q$ is:

$c_j = \sum_{i=1}^{s} k_{ji} f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).$
it being understood that $s\leq n$ , $t\leq q$ .

Let $Q$ contain no vanishing determinant of any order: Let $c_1$ , $c_2, \dots, c_{t}$ be a $t$ -element check, $t\leq q$ , on the operand sequence $f_1$ , $f_2$ , \dots, $f_{s}$, $s\leq n$. Let $v$ be a positive integer less than or equal to $s+t$ . If, in the transmittal of the sequence

$f_1, f_2, \dots, f_{s}, c_1, c_2, \dots, c_{t},$
errors occur in $v$ of its $s+t$ elements, whatever the distribution of the errors, the presence of error will certainly be disclosed, or will enjoy only a $1$ -in- $(\Gamma-1)^t$ chance of escaping disclosure, according as $v$ is, or is not, less than $t+1$ . In this statement, $\Gamma$ denotes the total number of elements in the field $F$ .

proof:
Case 1:
Let all $v$ errors fall among the $c_1, c_2, \dots, c_{t}$ . The presence of error is evidently certain to be disclosed.

Case 2:
Let all $v$ errors fall among the $f_1, f_2, \dots, f_{s}$.

(2.1): Let $v\leq t$ . There is no loss of generality of we assume [This assumption implies $v\leq s$ . – wdj] the $v$ errors are $\epsilon_1$ , $\epsilon_2, \dots, \epsilon_v$ , affecting $f_1, f_2, \dots, f_{v}$ . The errors cannot escape disclosure. For, to do so, they would have to satisfy the system of homogeneous linear equations:

$\sum_{i=1}^{v} k_{ji} \epsilon_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).$
in which the matrix of coefficients $k_{ji}$ contains no vanishing determinant of any order, and which, therefore admits no solution other than $\epsilon_i=0$ ( $i = 1, 2, \dots, v$ ).

For this treatment of the errors, compare Sections 4, 5.

Case 3:
Let $z$ errors fall among the $f_i$ and $w=v-z$ errors fall among the $c_j$ . Without loss in generality, we may assume that the errors are $\epsilon_1$ , $\epsilon_2, \dots, \epsilon_z$ , affecting $f_1, f_2, \dots, f_{z}$ , and $\delta_{j_1}$ , $\delta_{j_2}, \dots, \delta_{j_w}$ , affecting $c_{j_1}$ , $c_{j_2}, \dots, c_{j_w}$ .

(3.1): Let $z+w\leq t$ . Writing $t=v+h=z+w+h$ , where $h$ denotes a non-negative integer which may or may not be zero, we have $t-w = z+h$ . Hence $z+h$ of the $c_j$ are transmitted without error.

If the presence of error is to escape disclosure, we see, therefore, that the $z$ errors $\epsilon_i$ must satisfy the system of at least $z$ homogeneous linear equations:

$\sum_{i=1}^{z} k_{r_m,i} \epsilon_i,\ \ \ \ \ \ \ (m = 1, 2, \dots, z+h),$
where the indices $r_m$ denote a set of $z+h$ integers selected from $1, 2, \dots, t$ . But the matrix of coefficients in this system contains no vanishing determinant, so that the only solution would be $\epsilon_i=0$ ( $i = 1, 2, \dots, z$ ).

For details in this treatment of errors, see Section \ref{sec:5}.

(3.2): Let $z+w> t$ . Then $w = t-(z-h)$ , where $h$ denotes a positive integer. Assuming that the presence of error is to escape detection, we see, therefore, that the $v$ errors must satisfy $t$ linear equations as follows:

( $\alpha$ ) a system of $z-h$ equations involving only the errors $\epsilon_i$ , ( $i = 1, 2, \dots, z$ ), and homogeneous in these $z$ errors;

( $\beta$ ) a system of $w$ equations involving all $v$ errors.

Since the matrix of the coefficients in the system ( $\alpha$ ) contains no vanishing determinant, we can solve this system for $z-h$ of the $\epsilon_i$ as rational functions of the remaining $h$ of the $\epsilon_i$ .

The system ( $\beta$ ) determines all errors affecting the $c_j$ — that is, all the errors $\delta_{j_i}$ — as polynomial functions of the $\epsilon_i$ , ( $i = 1, 2, \dots, z$ ).

Hence, all told, $(z-h)+w$ errors are determined as rational functions of the remaining $h$ errors. In other words, $v-t$ errors determine the other $t$ errors.

An accidental error can assume any one of $\Gamma -1$ values, there being $\Gamma$ elements in the finite field $F$ . Hence the chance that the errors will check up, and thus escape disclosure, is only $1$ -in- $(\Gamma-1)^t$ .
QED

Lester Hill’s “The checking of the accuracy …”, part 13

Posted on 2015/02/05 by wdjoyner

Here is just the 14th section of his paper. I hope to post more later. (Part 13 is here.)

Illustration of checking in the field $F_{101}$

We wish to provide checks upon arbitrary sequences $f_1$ , $f_2$ , …, $f_n$ of elements of any given finite algebraic field. Operations in the field $F_{101}$ can be used to illustrate all the essential points arising in this connection.

Example 1: Check of Type A upon a sequence $f_1$ , $f_2$ , …, $f_{10}$ . Suppose that we wish, in a certain message, to transmit the numerical sequence

$38460000600800000299.$
The origin and significance of this sequence in the following form, in which it appears as a sequence of ten elements of $F_{101}$ :

$\begin{array}{cccccccccc} 38 & 46 & 00 & 00 & 60 & 08 & 00 & 00 & 02 & 99\\ f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 & f_9 & f_{10}\\ \end{array}$
A five-element check ( $q=5$ ) is obtained by the simple tabulation which follows. We use Table 4, noting that in each of the nine rows, the one-hundred columns are shown in four sections, there being twenty-five columns in each section.

For the first element, 38, in the operand sequence $f_i$ , place ruler under the proper section of row 1 of the Table. In row 1, read: 13 in column 38, 39 in column 13, 16 in column 39, 48 in column 16, 43 in column 48. Start a tabulation:

$13\quad 39\quad 16 \quad 48 \quad 43.$
For the second element, 46, in the operand sequence, place ruler under the proper section of row 2 of the Table. In row 2, read: 83 in column 46, 29 in column 83, 15 in column 29, 60 in column 15, 38 in column 60. Continue the tabulation:

$13\quad 39\quad 16 \quad 48 \quad 43\\ 83\quad 29\quad 15 \quad 60 \quad 38$
Since the third and fourth elements of the operand sequence are equal to zero, skip them entirely. For the fifth element, 60, read in row 5 of the Table: 76 in column 60, 2 in column 76, 16 in column 2, 27 in column 16, 14 in column 27. Continue the tabulation:

$13\quad 39\quad 16 \quad 48 \quad 43\\ 83\quad 29\quad 15 \quad 60 \quad 38\\ 76\quad 2\quad 16 \quad 27 \quad 14$

Proceed in this manner to the ninth element, 2, inclusive of the operand sequence. There being no tenth row in the Table, simply add the tenth element, 99, of the operand sequence in each vertical column of the tabulation. The full tabulation is:

$\begin{array}{rrrrrl} 13 & 39 & 16 & 48 & 43 & \\ 83 & 29 & 15 & 60 & 38 & \\ 76 & 2 & 16 & 27 & 14 & \\ 99 & 51 & 63 & 60 & 86 & \\ 84 & 94 & 9 & 75 & 19 & \\ \hline 454 & 314 & 218 & 369 & 299 & sum\ in\ ZZ\\ 50 & 11 & 16 & 66 & 97 & sum\ in\ F_{101}\\ \end{array}$
The five-element check is therefore:

$c_1 = 50, c_2 = 11, c_3 = 16, c_4 = 66, c_5 = 97.$
We transmit telegraphically the sequence of fifteen elements of $F_{101}$ :

$38 \quad 46\quad 00\quad 00 \quad 60\quad 08 \quad 00 \quad 00\quad 02\quad 99\quad 50 \quad 11\quad 16 \quad 66 \quad 97.$
A discussion of possible errors will be given in another section. we simply note here that the $c_j$’s, as determined in the above tabulation, are:

$c_1 = \sum_{i=1}^{10} a_i f_i,\quad c_2 = \sum_{i=1}^{10} a_i^2 f_i,\quad \dots, c_5 = \sum_{i=1}^{10} a_i^5 f_i.$
If only a one-element check had been desired, we should have taken $c_1=50$ , and a one-column tabulation would have sufficed. If a two-element check had been desired, we should have taken $c_1=50$ , $c_2=11$ and a two-column tabulation would have sufficed. Etc.

If the operand sequence $f_i$ contains less than $10$ elements, the procedure, to determine check of Type A, is obvious. A $q$ -element check upon $f_1$ , $f_2$ , \dots, $f_{n}$ , with $n<10$ , is as stated:

$c_j = \sum_{i=1}^{10} a_i^j f_i,\ \ \ \ \ \ \ j = 1, 2, \dots, q,$
with $q=1,2,3,4,5$ . The manner of its evaluation, by means of Table 4, is clear.

Example 2: Check of Type B upon a sequence $f_1$ , $f_2$ , … , $f_{8}$ .

Suppose that we desire a five-element check upon the numerical sequence $6500000000001794$ – that is, upon

$\begin{array}{cccccccc} 65 & 00 & 00 & 00 & 00 & 00 & 17 & 94\\ f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 \\ \end{array}$
We wish to evaluate $c_j = \sum_{i=1}^{8} b_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5)$ . The tabulation is as follows:

$\begin{array}{rrrrrl} 94 & 80 & 38 & 13 & 39 & row\ 1,\ Table\ 4,\ read:\ 94\ in\ column\ 65,\ etc. \\ 90 & 19 & 59 & 45 & 60 &row\ 7,\ read:\ 90\ in\ column\ 17,\ etc. \\ 94 & 94 & 94 & 94 & 94 & \\ \hline 278 & 193 & 191 & 152 & 193 & sum\ in\ ZZ\\ 76 & 92 & 90 & 51 & 92 & sum\ in\ F_{101}\\ c_1 & c_2 & c_3 & c_4 & c_5 & \\ \end{array}$

Example 3: Check of Type A upon the same operand sequence as in Example 2.

We wish to evaluate $c_j = \sum_{i=1}^{8} a_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5)$ . The tabulation is as follows:

$\begin{array}{rrrrrl} 94 & 80 & 38 & 13 & 39 & \\ 90 & 19 & 59 & 45 & 60 & \\ 97 & 41 & 9 & 34 & 5 &row\ 8,\ Table\ 4,\ read:\ 97\ in\ col.\ 94,\ etc. \\ \hline 281 & 140 & 106 & 92 & 104 & sum\ in\ ZZ\\ 79 & 39 & 5 & 92 & 3 & sum\ in\ F_{101}\\ c_1 & c_2 & c_3 & c_4 & c_5 & \\ \end{array}$

Example 4: Check of Type A and B upon the operand sequence

$\begin{array}{ccccccc} 00 & 65 & 00 & 00 & 00 & 17 & 94\\ f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 \\ \end{array}$
We wish to evaluate

$c_j = \sum_{i=1}^{7} a_i^j f_i= \sum_{i=1}^{7} b_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5).$
The tabulation is as follows:

$\begin{array}{rrrrrl} 58 & 30 & 19 & 76 & 1 & row\ 2,\ Table\ 4,\ read:\ 58\ in\ col.\ 65,\ etc. \\ 21 & 20 & 96 & 77 & 6 &row\ 6,\ read:\ 21\ in\ col.\ 17,\ etc. \\ 58 & 10 & 47 & 29 & 5 &row\ 7,\ read:\ 58\ in\ col.\ 94,\ etc. \\ \hline 137 & 60 & 162 & 182 & 12 & sum\ in\ ZZ\\ 36 & 60 & 61 & 81 & 12 & sum\ in\ F_{101}\\ c_1 & c_2 & c_3 & c_4 & c_5 & \\ \end{array}$

Questions of rigor will be discussed in a subsequent section. It may be noted here, however, that our checks make very
nice discriminations. Thus, although the operand sequence in Examples 3 and 4 are closely similar, the checking sequences are widely different.

It will now be apparent to those who are acquainted with the problems of code communication that we are in a position to furnish powerful and economical checks on message sequences in any conceivable telegraphic system. We have only to partition messages into groups of not more than ten, or not more that eight, elements each — according to any
definite prearrangement — and to check each group with a $q$ -check, $q=1,2,3,4,5$ (as may be arranged), of Type A or of Type B. If it is desired to work with longer groups, we have only to enlarge Table 4. The limitations introduced in this paper may be largely overcome, or removed, by suitable amplification of the Table employed.

Yet Another Mathblog

Category Archives: error-correcting codes