In memory of Solomon Golomb (1932-2016): author of a shift register with linear feedback of maximum length and poliomino

Original author: Stephen Wolfram
  • Transfer

Translation of Stephen Wolfram's post, " Solomon Golomb (1932–2016) ."
Many thanks to Polina Sologub for help in translating and preparing the publication.


- The most commonly used mathematical algorithm in history
- How I met Saul Golomb
- History of Solomon Golomb
- Shift registers
- Background of shift registers
- Why do we need sequences generated by shift registers?
Well, where are these registers?”
- Cellular automata and shift registers with nonlinear feedback
- Poliomino
- The rest of the story

The most commonly used math algorithm in history

Octillion . Billion billion This is a very rough estimate of how many times a mobile phone or other device has generated a bit using a shift register with linear feedback of maximum length . I think this is the most used mathematical algorithm in history. The author is Solomon Golomb , who died on May 1, whom we had known for more than 35 years.

The basis of the book of Solomon Golomb “Sequences of register shift” , published in 1967, was his work of the 1950s. And its content lives in each of the modern communication systems. Read specifications for 3G , LTE , Wi-Fi , Bluetooth, or even forGPS - and you will find references to polynomials defining the sequences generated by the shift registers, which these systems use to encode the data they send. Solomon Golomb is the man who created these polynomials.

In addition, he played an important role in calculating the distance to Venus using a radar, as well as in developing image encoding for sending from Mars. He introduced the world to what he called poliomino (which later inspired the creators of Tetris - “Tetromino tennis”). He created and solved countless math puzzles and puns. About 20 years ago I found out that he was very close to the discovery of my favorite rule 30 for cellular automata back in 1959, when I was just born.

How I Met Saul Golomb

I learned almost all the scientists and mathematicians I know through my professional connections. But not Sola Golomba. It was 1981, and I, a 21-year-old physicist (who became a little known in the media because I was the youngest recipient of the MacArthur Prize at the first award ceremony), was researching at the California Institute of Technology. There was a knock on the door of my office, and a young woman soon crossed the threshold. This was already unusual, because in those days where there were engaged in high-energy theoretical physics, there were hopelessly few women. Although I lived in California for several years, I nonetheless did not leave the university and was therefore ill-prepared for the surge of South California energy that burst into my office. The woman introduced herself to Astrid and said she was visiting Oxford and knew someone I was in kindergarten with. She explained that she was entrusted with collecting information about interesting people in the Pasadena area. I think she considered me a difficult case, but, nevertheless, insisted on a conversation. And once, when I tried to tell something about what I was doing, she said: "You should meet with my father. He is already an old man, but his mind is still razor sharp . "And it so happened that Astrid Golomb, the eldest daughter of Sol Golomb, introduced me to him.

The Golomb family lived in a house located in the mountains near Pasadena. They had two daughters: Astrid - a little older than me, an ambitious Hollywood girl, and Beatrice - about my age and scientific mentality. Golomb sisters often had parties - usually at home. Themes were different: this was a garden party and croquet with flamingos and hedgehogs ("the winner is the one whose costume is most Det fit topic"), or a Stonehenge-style party with instructions written by runes. At these parties young and not-so-good people intersected, including various local luminaries. And to them, a little aside, there was always a small man with a big beard, a little like the elf and always wore a dark coat - Solomon Golomb himself.

I gradually learned a little about him. That he was involved in the " theory of information ." That he worked at the University of Southern California . That he had various vague but apparently high-level n avitelstvennye and other links. I've heard of shift registers, but almost did not know anything about them.

In the fall of 1982, I visited Bell Labsin New Jersey and made a presentation on my latest findings in the field of cellular automata. One of the topics I discussed was “additive” (or “linear”), cellular automata , and their behavior with a limited number of cells . Whenever a cellular automaton has a limited number of cells, its behavior will ultimately inevitably be repeated ... However, as the size increases, the maximum repetition period, say, for rule 90 for an additive cellular automaton, seems to be completely randomimage: 1, 1, 3, 2, 7, 1, 7, 6, 31, 4, 63, ... However, a few days before the speech, I noticed that these periods seem to follow a formula that depends on prime factors or numbers cells. But when I mentioned this, one of those sitting far raised his hand and asked: “ Do you know if this works for n = 37? "In my experiments, I did not deal with this number, so I did not know. But why did someone ask me about it? The

one who asked me was called Andrew Odlyzhko - he was a theoretician from Bell Labs. I asked him:" What does it make you think that something special could be connected with n = 37 ? "." Well, "he said,"I think that what you are doing is related to linear feedback shift theory of registers, "and he suggested that I looked at Sol Golomb’s book." Oh yes, "I said," I know his daughters .. . "Andrew was right: there is a very elegant theory of additive polynomial-based cellular automata, analogous to Saul's theory developed for linear feedback shift registers. Andrew and I wrote a rather well-cited article about this (this is a rare case when traditional mathematical methods allow to describe the behavior of cells th machine). A few things was that I learned to have a side effect of what is involved in Solomon Golomb (if you remember, this was all before the Internet).

The Story of Solomon Golomb

Solomon Golomb was born in Baltimore, Maryland , in 1932. His family was from Lithuania . His grandfather was a rabbi, and his father still very young moved to the United States and received a master's degree in mathematics, after which he went into medieval Jewish philosophy and also became a rabbi. Sol’s mother came from a well-known Russian family who made boots for the tsar’s army, and then led the bank. Sol excelled at school, being the strongest in debate. Inspired by his father, he became interested in mathematics and at the age of 17 published an article on prime numbers. After graduating from high school, he enrolled at Johns Hopkins Universityto study mathematics, and almost fell into the quota for Jewish students (so he had to promise that he would not go to medicine, and then Sol, having doubled his workload, graduated from the university in 1951 in half the usual term of study).

From there, he went to Harvard to graduate school in mathematics. However, before that, he worked in the summer at the Glenn L. Martin Company , an aerospace company founded in 1912 that moved to Los Angeles in the Baltics in the 1920s and became a defense contractor, which eventually turned into Lockheed Martin. At Harvard, Sol specialized in number theory, and, in particular, in characterizing sets of primes. But every summer he returned to the Martin Company. As he said later, at Harvard, "the question of whether any practical application had what they taught and learned there, it was impossible even to say it out loud, not to mention discussing it ." But at the Martin Company, he found that the pure mathematics that he knew — even prime numbers — did indeed have practical applications, including the shift register.

In the first summer of his work at the Martin Company, Sol was assigned to a management theory group. In the second summer, he was placed in a communications study group. And in June 1954, it happened that his boss attended a conference, where he heard about the strange behavior of the linear shift feedback register shift, and he asked Saul if he could do this research. Soon, Sol realized that this topic could be explored with the help of polynomials over finite fields. The next year, he divided his time between Harvard graduate school and consulting for the Martin Company, and in June 1955 he wrote his final report, “ Sequences with Random Properties, ” which became fundamental to the shift register theory.

Sol loved math puzzles, and while pondering puzzles with arranging domino tiles on a chessboard, he invented what he later called " poliomino ." He gave a talk about them in November 1953 at the Harvard Mathematics Club, published an article about them (his first research work), and won a Harvard Mathematics Award for working with them.

In June 1955, Sol went to Oslo University for a year on the Fulbright Fellowship program.- partly in order to work with some prominent theorists, partly in order to learn Norwegian, Swedish and Danish (and learn some runic manuscripts) and replenish your collection of language skills. During his stay in Oslo, he completed a long article on prime numbers and managed to travel around Scandinavia, and in Denmark he met a young woman named Bo (Bodil Rygaard) - she was from a large family and was born in a countryside known only for its peatlands moss, but managed to get to university and studied philosophy. Sol and Bo seemed to get along and got married a few months later.

When they returned to the United States in July 1956, Saul gave several interviews and then joined the JPL- Jet Propulsion Laboratory, which was separated from the California Institute of Technology and was engaged in military development. Sol was included in the communications team as a senior research engineer. This was when people from the laboratory were ready to launch the satellite. However, the government did not allow them, fearing that it would look like military action. Everything changed in October 1957, when the Soviet Union launched its satellite, allegedly as part of the International Geophysical Year . Surprisingly, it took the United States just 3 months to launch Explorer-1. JPL did a lot to launch the satellite, and the Sol group (where technical specialists worked on the implementation of the register shift in electronic form) was sent to create radiation detectors; during this job, Sol was able to return briefly to Harvard to pass the final PhD exams.

It was a time of concentration around the JPL and the space program. In May 1958, a new information processing group was formed, headed by Sol, and in the same month his first child was born - Astrid. Sol continued his study of the sequences generated by the shift registers for jamming resistant rockets. In May 1959, Sol's second daughter appeared, who was named Beatrice (good sequence: A, B ...). In the fall of 1959, Sol took an academic leave at MIT , where he met Claude Shannon and a number of other MIT luminaries and studied theories of information and algebraic codes.

At that time, he had already done some work on coding theory in the field of biology. Despite the fact that the digital nature of DNA was discovered by Jim Watson and Francis Crick back in 1953, it was still not clear how exactly the sequences of the four possible base pairs encode 20 amino acids. In 1956, Max Delbrück- Watson's former adviser on a postdoc at California Tech - consulted with the Jet Propulsion Laboratory on this issue. Sol and two of his colleagues analyzed Francis Crick's idea and came up with “comma-free codes” in which overlapping triples of base pairs can encode amino acids. The analysis showed that exactly 20 amino acids can be encoded in this way. This was one of the most amazing explanations; but, unfortunately, biology actually does not work that way (biology uses simpler coding, in which some of the 64 possible triples do not represent anything).

In addition to biology, Sol also studied physics. Its sequences generated by the shift registers were useful for calculating the range using the radar (used in GPS); also Sol was appointed responsible for finding the distance to Venus. And it so happened that in early 1961, when the Sun, Venus and Earth lined up most successfully, Sol, using the 85-foot Goldstone radio antenna located in the Mojave Desert , received a radar signal from Venus and clarified the data we have on Earth-Venus distances and Earth-Sun.

Given Sol's interest in languages, coding, and space, it is not surprising that he became interested in aliens. In 1961, he wrote an article for the Air Force entitled "A short manual on extraterrestrial linguistics, "and over the next few years he wrote several articles on this topic for a wider audience. He said: " There are 2 main problems regarding contact with aliens: one of them is the problem of finding a mutually acceptable channel. The other is more philosophical problem (semantic, ethical and metaphysical), which consists in finding the right subject for discussion. Simply put, first we need to find a common language, and then we need to think what to say . "Then it is peculiar he continued with humor: "Naturally, we should not tell them too much until we find out if they have enough noble intentions. The government will undoubtedly create a Space Intelligence Agency (KRU) to monitor extraterrestrial intelligence. Extreme security measures will be taken. As Herbert Wells once remarked [or was it an episode from the Twilight Zone ?] That even if the aliens tell us with all sincerity that their only goal is to “serve humanity”, we must find out if they want to serve us in the baked or in fried. "

During his work in the JPL lab, Sol also taught at nearby universities: the California Institute of Technology, the University of Southern California, and the University of Los Angeles. In the fall of 1962, after changing the situation in the laboratory (and perhaps because he wanted to spend more time with his young children), he decided to become a full-time professor. He received offers from all three universities. He wanted to go where he could work freely. He was told that at the California Institute of Technology " no one but the Nobel laureates has any influence, " and in Los Angeles, "there is such a bureaucracy that no one can influence anything ." As a result, Sol chose the University of Southern California, even despite his low reputation. In the spring of 1963, he began work as a professor of electrical engineering and eventually worked there for 53 years.

Shift registers

Before continuing the story of Saul's life, I must explain what the linear feedback shift register (LFSR) is. The basic idea is quite simple. Imagine a series of squares, each containing 1 or 0 (say, black or white). In a pure shift register, everything that happens is reduced to shifting all values ​​one step to the left, while the leftmost value is lost, and the new value is taken to the right. The idea of ​​a feedback shift register is that the value that is shifted is determined (or “fed back”) depending on the values ​​of other positions in the shift register. In a linear shift register with feedback, the values ​​from the “branches” at certain positions in the register are combined modulo 2 (so that 1⊕1 = 0 instead of 2), or XOR (“ exclusive or ”) is applied .

Here's what happens after a while:

As you can see, the shift register always shifts bits to the left, and other bits are added to the right according to a simple rule. The sequence of bits seems random, although, as shown in the figure, it eventually repeats. Sol Golomb found an elegant mathematical way to analyze such sequences and how they are repeated.

If the shift register has size n, then it has 2 n possible states (corresponding to all possible sequences 0 and 1 with length n) Since the rules for the shift register are deterministic, any given position should always come to a different same position. This means that the maximum possible number of steps that the shift register can go through before the steps begin to repeat is 2 n (in fact, 2 n - 1, since the position with all 0 cannot evolve into anything else).

In the above example, the shift register has size 7 and will repeat exactly after 2 7 - 1 = 127 steps. But which shift registers — with which branch locations — will produce sequences of maximum length? This question Solomon Golomb began to investigate in the summer of 1954. And his answer was simple and elegant.

The shift register above has branches at positions 7, 6 and 1. Sol presented this algebraically using the polynomial x 7 + x 6 + 1. He showed then that the generated sequence will be of maximum length if this polynomial is “ irreducible modulo 2 ”; therefore, it cannot be factorized, which makes it an analogue of a prime among polynomials; and the presence of some other properties makes it a " primitive polynomial ." Today, this is easy to verify using the Mathematica system and the Wolfram Language :

Then, in 1954, Sol had to do all this manually; he compiled a rather long table of primitive polynomials corresponding to shift registers, which produced sequences of maximum length:

Shift Register Background

The idea of ​​maintaining RAM through the " delay lines " that transmit digital pulses dates back to the beginning of the era of computers. By the end of the 1940s, such delay lines were applied digitally using a series of vacuum tubes and were called “ shift registers ”. It is not clear when the first feedback shift registers were created. Perhaps this was in the late 1940s. However, this event is still shrouded in mystery, because for the first time they were used in military cryptography.

The main idea of ​​cryptography is to change meaningful messages in such a way that they cannot be recognized; however, if you know the key, you can recreate the encrypted message. The so-called stream ciphers work on the principle of creating long sequences of random elements, as it were, and are decoded using a receiver that independently generates the same sequence of elements.

Linear feedback shift registers have been valued in cryptography due to long repetition periods. However, the mathematical analysis that Sol used to find these periods makes it clear that such shift registers are not suitable for secure cryptography. However, at the beginning they seemed to be quite good (especially in comparison with the successive rotor positions in Enigma); persistent rumors circulated that Soviet military cryptosystems were built on this basis.

Back in 2001, when I was working on historical notes for my book A New Kind of Science , Sol and I talked for a long time over the phone about register shifts. Saul told me that when he started, he knew nothing about cryptographic work on shift registers. He said that employees at Bell’s laboratory, Lincoln’s laboratory, and Jet Propulsion Laboratory began working on the shift registers at about the same time that he did; however, he managed to advance a little further, which he noted in his report of 1955.

Over the following years, Sol gradually learned about the various predecessors of his work from literature on pure mathematics. Already in 1202Fibonacci talked about what is now called Fibonacci numbers and which are generated by a recurrence relation (which can be considered as an analogue of the linear feedback shift register that works with arbitrary integers rather than zeros and ones). There are also small works of the early 1900s on the cycles of 0 and 1, but the first large-scale study was the work of Oysten Ore from the University of Oslo. Ore had a student named Marshall Hall who advised a predecessor to the National Security Agencyin the late 1940s - probably on the subject of shift registers. However, everything he did was classified, and therefore he arranged with Sol to publish the history of shift registers with linear feedback; Saul dedicated his book to Marshall Hall.

Why do we need sequences generated by shift registers?

I have noticed many times that systems defined by simple rules end up with many application variations; shift registers also follow this pattern. Both modern equipment and software are crammed with shift registers: there are probably a dozen or two of them in an ordinary mobile phone, which are usually implemented at the hardware level, and sometimes in software (when I write here “shift register”, I I mean the linear feedback shift register - LFSR).

In most cases, shift registers are used that give sequences of maximum length (otherwise known as " M-sequences""). The reasons they are used are usually related to some of their properties that Sol discovered. They always contain the same amount of 0 and 1 (although in fact there is always exactly one extra 1). Subsequently, Sol showed that they the same number of sequences 00, 01, 10 and 11 is also characteristic - and for large blocks too, this property of " balance " is already very useful in itself, for example, if you test all possible combinations of bits as input.

However, Sol found another, even more important property. Replace each 0 in the sequence with 1, then multiply each element in the shifted version of the sequence with the corresponding element in the original. Sol showed that when added, these elements will always be zero (except when there is no shift at all). That is, the sequence has no correlation with shifted versions of itself.

These properties will be true for any sufficiently long random sequence of 0 and 1. It is surprising that for sequences of maximum length these properties are always true. Sequences have some traits of randomness, but in reality they are not at all chaotic: they have a well-defined, organized structure .

It is this structure that is characteristic of linear feedback shift registers that makes them unsuitable for serious cryptography. But they are great for basic "rearrangement of elements" and cheap cryptography and are actively used for these purposes. Often the task is simply to “whiten” the signal (as in “white noise”). Sometimes you need to transfer data with long sequences of 0. But the electronics in this case can get confused if the "silence" is too long. You can avoid this problem by scrambling the source data by combining it with the sequence generated by the shift register. This is exactly what was done with Wi-Fi , Bluetooth , USB , digital TV , the Internet , etc.

A side effect of the shift register scrambling is more complex decoding, which is sometimes used to increase security ( DVD technology uses a combination of shift registers with a length of 16 and 24 bits for encoding data; many GSM phones use a combination of three shift registers to encode all signals).

In GPSshift register sequences are also used. Each GPS satellite continuously transmits a sequence generated by a shift register of 10 bits in length. Based on the received part of the sequence, the receiver can accurately determine at what time the signal it received was sent from a particular satellite. And then, by comparing the time delay from different satellites, the receiver can triangulate its position (there is also a GPS mode using a shift register with a length of 1024 bits).

In a completely different way, shift registers are used to detect errors. Say someone sends blocks of bits, and for each of them there is a small probability of error. A simple way to check for a single error is to enable the " parity bit. "", which tells you how many 1 (odd or even number) should be in the block of bits. You can also use CRC (cyclic redundancy checks), which can look for more errors, and they are calculated by submitting data to the shift register with linear feedback There are also error correction codes that allow not only detecting, but also correcting a certain number of errors, and some of them can also be calculated using the sequences generated by the shift registers - and Sol Golomb used He called versions of these codes, called Reed-Solomon codes , for encoding video for a spacecraft to Mars.

The scope of sequences generated by shift registers is getting wider. There is a rather exotic example of using sequences generated by shift registers to clock jitter in a computer - decomposing the frequency at which the processor can potentially generate radio frequency interference (select “Enable Spread Spectrum” in the BIOS).

One of the most famous uses of shift register sequences is CDMAPhones (Code Division Multiple Access). Cell phones got their name because they work in “cells”, and all phones of a certain cell are connected to a certain tower. But how do different cell phones in the “cell” not interfere with each other? In the first systems, each telephone simply “agreed” with the tower to use a slightly different frequency. Later, various time slices began to be used ( TDMA - time division multiple access). And CDMA, as a reasonable alternative, uses maximum length shift register sequences.

The idea is that all phones work on the same frequency, but each phone encodes its own signal using (in the simplest case) different versions of the sequences generated by the shift registers. According to Sol's results, different shift options do not correlate with each other, and therefore mobile phone signals do not interfere. This is how most 3G networks work .

Sol created the mathematical basis for all this, and also re-introduced each other to a number of key figures. Back in 1959, he met with Irwin Jacobs , who recently received his doctorate from the Massachusetts Institute of Technology. He also knew Andy Viterbi.who worked at the Jet Propulsion Laboratory. Sol introduced them, and in 1968 they founded a company called Linkabit , which worked on coding systems (mainly for military purposes).

In 1985, Jacobs and Viterbi founded another company called Qualcomm . At first, things were not going well with them, but by the beginning of the 1990s, when they began to produce components for deploying CDMA in cell phones, the company began to grow rapidly.

Well, where are these registers?

Surprisingly, most people have never heard of shift registers and at the same time interact with them whenever they use modern communication systems, computer technology, etc. It’s easy to get confused, given that the same sequence of registers are behind different names and abbreviations linear feedback shift (PN, pseudo noise, M-, FSR, LFSR sequences, MLS, SRS, PRBS, etc.).

If we consider mobile phones, then the use of sequences generated by shift registers in them has changed over the years, increasing and decreasing. 2GNetworks are based on TDMA, so they do not use the sequences generated by the shift registers to encode their data, but they still often use CRC (cyclic redundancy code) to check data blocks. 3G networks are the largest users of CDMA, so the sequences generated by the shift registers are involved in the transmission of each bit. 4G networks usually use a combination of time and frequency of slots that do not include shift register sequences, although CRCs are still used: for example, to interact with integral data when the frequency windows overlap. 5gIt has a more complex structure - with many antennas that dynamically adapt to use the optimal time and slot frequency. However, half of their channels are usually allocated for “pilot signals”, which are used to derive the local radio environment; they are also based on the sequences generated by the shift registers.

In the production of electronics, they usually try to achieve the highest data transfer rate with minimal energy consumption, allowing the bits to overcome the noise threshold. And, as a rule, this way leads to the automation of error detection, and, therefore, to the use of CRC (cyclic redundancy code) and, therefore, the sequences generated by the shift register. This applies to almost all types of buses inside the computer ( PCIe ,SATA , etc.): providing the interaction of parts of the central processor, or receiving data from devices, or connecting to a display with HDMI . In the case of disks or memory, CRC and other codes based on the sequences generated by the shift registers are also almost universally used to operate at maximum speed.

Shift registers are so ubiquitous that it is almost impossible to estimate how many bits they generate. There are approximately 10 billion computers, a little less - phones, and a huge number of devices in the built-in IoT ("Internet of things") . Almost every car in the world (and there are more than a billion of them!) Has about 10 built-in microprocessors.

At what frequency do shift registers work? In communication systems, there is a base carrier frequency in the hertz range, as well as a "signal element transmission rate", which indicates how quickly multiple access is performed (we are talking about CDMA) in the MHz range. On the other hand, in buses inside computers, all data is transmitted using shift registers - with the best transfer speed in the hertz range.

There are at least 10 billion communication lines operating at least 1/10 billion seconds (about 3 years) that use at least 1 billion bits from the shift registers every second, which means that the Sol algorithm was used at least an octillion times.

Is this algorithm really used most often? I think yes. I suspect that only arithmetic operations can compete. Today, processors are capable of performing a trillion arithmetic operations per second, and such operations are necessary for almost every bit generated by a computer. But how is arithmetic performed? At some level, it's just an implementation of digital electronics.

However, there are “algorithmic ideas” that remain incomprehensible to everyone except microprocessor designers. When Babbage made his difference machine (see the article on Habra " Untangling the story of Ada Lovelace (the first programmer in history)"), transfers became a big obstacle to arithmetic operations (in fact, a shift register with linear feedback can be thought of as a system that does something like arithmetic calculations but does not carry out transfer). There are" transfer signal propagation trees "Optimizing hyphenation. There are also small tricks (like the" Booth algorithm "," Wallace trees", etc.), which reduce the number of bit operations necessary to create the" internals "of arithmetic. But, unlike shift registers with linear feedback, a single algorithmic idea that would be used almost anywhere just does not exist; therefore I think that the longest possible sequences generated by linear feedback shift registers still win among the most used sequences.

Cellular automata and shift registers with nonlinear feedback

Although this does not seem obvious at first glance, it turns out that there is a close relationship between shift registers with feedback and cellular automata, which I have studied for many years. The basic organization for a feedback shift register is to compute one bit at a time. There is one line of cells in a cellular automaton, and at each step, all cells are updated in parallel, based on a rule that depends, for example, on the values ​​of their nearest neighbors.

To see how they are related, you need to start the shift register with feedback of size n , and at the same time display its status only every nsteps; in other words, allow all bits to be overwritten before they reappear. If each step of the shift register with linear feedback is displayed (here with two branches), then at each of the steps everything will shift to the left - and that’s it. But if you make a compressed picture, showing only every n steps, you will see a pattern.

This is a nested pattern; and this picture is very similar to that which can be obtained if the cellular automaton takes the cell and the neighboring one and adds them modulo 2 (XOR). This is what happens with a cellular automaton if it arranges its cells so that they are in a circle of the same size as the shift register above:

Initially, cellular automata and shift register patterns turn out to be exactly the same. If you look at these pictures, it becomes less surprising that the mathematics of shift registers should be related to cellular automata. And, given the repeatability of nested patterns, it becomes clear why an elegant mathematical theory of shift registers must exist.

For typical shift registers used in practice, such explicitly repeating patterns are not characteristic. Here are some examples of shift registers that generate sequences of maximum length. The fact is that the branches are far apart, which makes it difficult to find visual traces of nesting.

How wide is the correspondence between shift registers and cellular automata? For cellular automata, the rules for generating new cell values ​​can be anything. In linear feedback shift registers, they should always be based on modulo 2 (or XOR) addition. This is what the “linear” part of the “linear feedback shift register” means. It is also possible to use any rule to combine values ​​for shift registers with non-linear feedback (NFSR).

Indeed: when Sol developed his theory for linear feedback shift registers, he began with a nonlinear case. When he arrived at JPL in 1956, he received a laboratory equipped with racks for small electronic modules. Saul said the modules (each one the size of a cigarette pack) were built for the Bell Labs project to perform a specific logical operation (AND, OR, NOT, ...). The modules can be used together to implement any desired non-linear feedback shift registers, providing about a million bits per second (Sol told me that someone tried to do the same using a universal computer, and that took 1 second when using hardware modules, it took 6 weeks to work on a universal computer).

When Sol began to study shift registers with linear feedback, his first serious discovery was the periods of their repetition. And in the case of non-linear, he directed most of his efforts to trying to understand the same thing. He collected all kinds of experimental data. He told me that he even checked sequences of 2,445 , which took a year. He made a summary, as in the picture below (pay attention to the visualization of the sequences shown on the waveform line). But he never managed to come up with some kind of general theory, which he had for linear feedback shift registers.

No wonder he couldn't do it. Already in the 1950s, theoretical results appeared (in most cases based on the ideas of universal Turing computations), of which programs, in principle, could do this. I don’t think Sol or anyone else ever thought that very simple (non-linear) functions would be used in shift registers with non-linear feedback.

And only later it became clear how complex the behavior of even very simple programs can be. My favorite example is rule 30 for a cellular automaton, in which the values ​​of neighboring cells are combined using a function that can be represented as p + q + r + q * r mod 2 (or p XOR ( q OR r )) Incredibly, Sol considered shift registers with non-linear feedback based on similar functions: p + r + s + q * r + q * s + r * s mod 2 . Here, below, are illustrations of how the Sol function (which can be regarded as the “ rule 29070 ”), rule 30, and several other similar rules look in the shift register:

But here, they are not limited to a fixed-size register, they look like cellular automata:

Of course, Sol never made pictures like this (and it was almost impossible to do in the 1950s). Instead, he focused on the repetition period as a kind of aggregate characteristic.

Saul wondered if shift registers with nonlinear feedback could be sources of randomness. From what is known today about cellular automata, it is clear that they can. For example, to create randomness for the Mathematica system, we used the rule of 30 cellular automata for 25 years (although we recently abandoned it in favor of a more efficient rule, which we found by studying trillions of possibilities).

Sol spoke a little about encryption; although I think he did not work for the government for long. He told me that, although in 1959 he discovered “ multidimensional correlation attacks on non-linear sequences, ” he “ carefully avoided allegations that the program was for cryptanalysis"The fact is that rule 30 for cellular automata (and possibly also shift registers with non-linear feedback) can be good cryptosystems - although due to the fact that they seem to be equivalent to shift registers with linear feedback (and this not), they have never been used as much as possible.

As an enthusiast, over the past few decades I tried to study all the predecessors of my work on one-dimensional cellular automata. Two-dimensional cellular automata were a little studied, but in the case of od only one purely theoretical work was found by numbers. I think that from all that I saw, the shift registers with non-linear feedback of Solomon Golomb were closest to what I eventually did a quarter century later.


Hearing the name " Golomb ", many will recall the shift registers. However, most will remember about poliomino . Sol did not invent poliomino, although he coined the name. He made systematic what used to appear only in individual puzzles.

The main question Sol was interested in was how poliomino sets could be organized, covering a certain area. Sometimes it’s pretty obvious, and sometimes it’s pretty complicated. Sol published his first article on poliomino in 1954, but Martin Gardner made poliomino really popular in 1957 (he wrote a column on mathematical games in Scientific American) As Sol explained in the preface to his book of 1964, as a result he received "a constant stream of correspondents from all over the world and from all walks of life: chairmen of the board of directors of leading universities, residents of unknown monasteries imprisoned from famous prisons ... ".

Game companies also turned their attention to new puzzles, and headlines like “ new sensational puzzles ” appeared over the course of several months, followed by decades of other puzzles and poliomino-based games (no, the sinister bald guy doesn't look like Sol): Sol printed articles about poliomino for another 50 years after the first publication. In 1961, he introduced options for dividing into small parts " rep-tiles

", with which you can create fractal (" Infin-tile ") patterns. But almost everything Sol did with poliomino included solving specific problems.

I am not much interested in the specifics of poliomino; I'm interested in related phenomena of a more general nature . It seems that it is easy to decide whether it is possible to “bridge” the entire plane with a few simple forms, but in the case of poliomino (as well as with all games and puzzles based on them), it becomes clear that everything is not so simple. indeed - in the 1960s it was proved that this task was theoretically nical unsolvable .

If we are only interested in a limited area, then, in principle, you can simply list all conceivable arrangements of figures, and then see if they are arranged in the right way. However, if we are interested in infinity, then this can not be done. Maybe someone will find the option of successfully placing a million pieces, but there is no guarantee that this result can be distributed further.

Turns out it might look like a working Turing machine- or a cellular automaton. You start with a line of tiles. Then the question of whether infinite tiling is possible is equivalent to the question of whether installation is possible for a Turing machine, which will enable it not to stop. The fact is that if the Turing machine is universal (that is, it can be programmed to perform any possible calculations), then the stop problem for it can be unsolvable, which means that the tiling problem will also be unsolvable.

Of course, this depends on the original set of forms. The question is how complicated the forms must be in order to code universal computations and lead to the insoluble problem of tiling. Solomon Golomb knew about the literature on this topic, but was not particularly interested in it.

It is known that sophisticated and carefully designed polimino sets actually support universal computing. But what about a simple set? Is he really simple enough to accidentally stumble upon him? If you look at all the systems that I studied, then the simplest set really turns out to be simple. However, it is difficult to find.

A much simpler task is to find poliominoes that successfully fill planes, although only non-periodically. Roger Penrose found a suitable example in 1994 . In my book A New Kind of Science, I gave a slightly simpler example with 3 poliominoes:

Rest of the story

Saul was a little over thirty when he achieved notable success in the field of shift registers and poliomino ... He was a very active person. He wrote several hundred articles , some of which expanded his earlier works, some were answers to questions that he was asked, and some were written, it seems, just for fun - to find out interesting things about numbers, sequences, cryptosystems, etc. e.

Shift and poliomino registers are voluminous topics (they are even put into separate categories in the AMS classification) In recent decades, they both received a new round of development, when they began to conduct computer experiments on their basis; Sol also took an active part in them. However, many questions remain unanswered. And if large Hadamard matrices can be found for shift registers with linear feedback , then even now little is known about shift registers with non-linear feedback, not to mention all non-periodic and other exotic poliominoes.

Sol has always been interested in puzzles, both math and words. For some time he led a column of puzzles for the Los Angeles Times , and for 32 years he wrote " Golomb Gambits " in John Hopkins alumni magazine. He took part in testing MegaIQand won a trip to the White House when he and his boss entered the top five in the country.

He put a lot of effort into his work at the university: he not only taught students and supervised graduate students and climbed the administrative ladder (president of the university council, vice-rector for research, etc.), but also expressed his opinion on managing the university as a whole (for example, wrote an article entitled "Consulting at the faculty: to remove or leave?" ; Answer: no, this is good for the university!). At the University of Southern California, he was engaged in headhunting, and during his work there he helped the university rise from the unknown to the top of the rating of educational programs.

And then there was consulting. Sol was meticulous and did not disclose what he was doing for government organizations. At the end of the 60s, disappointed that everyone except him was engaged in the sale of games based on poliomino, Sol founded the company, which he called Recreational Technology, Inc. Things were not going well, but Sol met Alvin Burlekamp , a professor at Berkeley who was keen on coding theories and puzzles. Subsequently, they founded Cyclotomics (in honor of cyclotomic polynomials of the form x n - 1), which was eventually sold to Kodak for a round sum (Berlekamp also created an algorithmic trading system, which he then sold to Jim Simonsand which became the starting point for Renaissance Technologies - one of the largest hedge funds to date).

More than 10,000 patents are somehow related to the work of Saul, but Sol himself received only one patent for cryptosystems based on quasigroups - and I think that he did little to commercialize his work.

Over the years, Sol has worked with the Technion , an Israeli Institute of Technology. He spoke of himself as a “ non-religious orthodox Jew, ” but at the same time he sometimes taught seminars on the Book of Genesis for beginners, and also worked on deciphering parts of the Dead Sea scrolls (Qumran manuscripts).

Saul and his wife traveled a lot, but Saul’s “center of the world” was definitely his Los Angeles office at the University of Southern California, and the house he and his wife had lived in for nearly 60 years. He was always surrounded by friends and students. And he had a family. His daughter Astrid played the role of a student in a play about Richard Feynman (she posed for him), and in my friend’s novel as one of the characters. Beatrice devoted her career to applying the mathematical level of accuracy to various types of medical indications and diagnostics (diseases associated with the Gulf War, statin effects, hiccup attacks, etc.). I even made a small contribution to Beatrice's life by introducing her to the man who later became her husband - Terry Seinowski, one of the founders of modern computational neuroscience.

It seemed that Saul was involved in many events, even if he did not spread too much about the details. From time to time I wanted to talk with him about science and mathematics, but he was more interested in telling stories (often very fascinating) both about individuals and organizations (" Can you believe that [in 1985], after many years of absence at conferences, Claude Shannon just appeared without warning at the bar at the annual conference on information theory? ";" do you know how much they had to pay the head of the California Institute of Technology to get him to go to Saudi Arabia ? ", etc.) .

Looking back, I understand that I would like to interest Saul in solving some of the mathematical issues raised in my work. I think that I still did not understand the extent to which he liked to solve the problems proposed by other people. Despite a significant contribution to the development of the computing world infrastructure, Sol himself never used computers seriously. He was very proud that he could easily carry out calculations in his mind. Until the age of 70, he did not use e-mail and never used a computer at home, although he had a mobile phone (he practically didn’t receive regular email. I mentioned once that about a year ago I was studying the history of Ada Lovelace ; he replied: "The story of Ada Lovelace as the Babbage programmer is so widespread that everyone seems to accept it as a fact, but I have never seen sources on this subject. ").

Saul’s daughters organized a party about his 80th birthday a few years ago and created such interesting invitations:

Saul had certain health problems, although it seemed that this did not really affect his rhythm of life. His wife’s health was deteriorating, and the last few weeks rather sharply. The Sol on Friday as usual, went to his office, and on Saturday night he died in his sleep. his wife Bo survived him for two weeks and died just two days before the 60th anniversary of their wedding.

while Saul and left, his work lives in octillion bits in the digital world.

P oschay, Saul and all of us -. thanks.

Also popular now: