In the automatic train control system at our transit agency, we use something called a "Checked Redundant" processor that handles all the safety critical functions.

The architecture of the processor resembles three PLCs which are cross checked so all three must arrive at the same decision to activate some external device (like operating track switches or issuing a "permissive" speed code to the trains).

However the manual refers to an algorithm called "Polynomial Division" to evaluate the Boolean expressions representing all the variables which are used to determine the final decision.

So what exactly is a Boolean Polynomial and what is polynomial division?

 

It is like a polynomial over the real numbers except that:

1. Coefficients can only be 0 or 1.
2. The addition operation is replaced by an Exclusive-OR
3. The multiplication operation is replaced by a Left-shift

For example:

x^4 + x^2 +1

represents the binary number --> 10101

When used in an equation such as

x^4 + x^2 + 1 = 0

You can exclusive-or x^4 with both sides and get

x^2 +1 = x^4

This says that if you express any 4-bit number as a boolean polynomial and multiply it by x, if you get a 1 for the coefficient of x^4, you can exclusive or x^2+1 to the rightmost 4 bits and discard the x^4 term.

I don't necessarily expect this to be a satisfactory answer and I'm a bit disappointed in the top Google hits for a better explanation. If you like try searching for "cyclic redundancy check" or CRC.

 

However the manual refers to an algorithm called "Polynomial Division" to evaluate the Boolean expressions representing all the variables which are used to determine the final decision.
__________________
aliiii

 

What manual are we talking about? Can you give us a link so we can help you answer your question?

I have no idea how polynomial division relates to your specific system and the way it makes decisions. If you can multiply two polynomials together and get a polynomial, then you should be able to divide one polynomial by another and get a polynomial so long as the divisor is not identically 0.

 

Note that zeeshan030 simply copied a part of the OP on a dated thread. Probably a bot.

 

Note that zeeshan030 simply copied a part of the OP on a dated thread. Probably a bot.

Your observation is simpler and according to Occam's razor probably the correct explanation. I was thinking that zeeshan030, the understudy, took over for Glenn Holland after he got fired for not being able have the members of the forum solve his 'Homework Problem'.

I went back to an old source and I think what is going on is that rather than having the separate systems check all their data bit by bit, they compute a CRC, which is the same as polynomial division, and they compare the CRC's. If each machine computes the same CRC, then all of the bits that went into the calculation must have come from identical bit streams. It also went by the name signature analysis in my 35 year old reference.

http://www.amazon.com/Digital-Hardware-Design-John-Peatman/dp/0070491321/ref=sr_1_1?ie=UTF8&qid=1428601764&sr=8-1&keywords=Peatman, digital Hardware Design

A bargain at $0.36

 

Leaving the issue of live or Memorex (bot) aside, I agree that the systems are probably comparing CRC values. This is pretty common. It is also a bit risky as the collision opportunities in most CRC computations are surprising high (which is really saying that they are very low, but not nearly as low as the people choosing to use them often believe).

 

Leaving the issue of live or Memorex (bot) aside, I agree that the systems are probably comparing CRC values. This is pretty common. It is also a bit risky as the collision opportunities in most CRC computations are surprising high (which is really saying that they are very low, but not nearly as low as the people choosing to use them often believe).

It has a great deal to do with the length of the message and the length of the CRC. In communications and disk drives, for the purposes of error detection, 16 to 32 bits were used for blocks of 256 to 512 bytes. Very few codewords for a huge quantity of possible messages. What you'd like to think is that the Hamming distance between two messages that compute the same codewords is large, or at the very least -- not small.

 

The problem is compounded by the total number of messages. Let's just take a 32-bit CRC. That's a maximum of about 4 billion check values. For any given pair of random messages, I expect a collision to occur with a probability of one in four billion. That sounds pretty impressive. But if I am generating thousands of messages a second, that results in a pretty high error rate. At 1000 messages/sec I expect to see a collision (again, from random message pairs) about every 50 days. If I have a hundred systems operating at the same time, then I expect it to happen a couple times a day. While that is still a low probability (and it is lower than this example since you have to multiply it by the failure rate of the system to begin with), the question is whether it is acceptably low for a safety-critical system.

As for the Hamming distance issue, I agree. The problem is that the CRC is not designed to maximize the Hamming distance between colliding messages.

Even worse is that constructing a message that collides with a given CRC value is pretty straightforward. For non-adversarial situations, such as protecting against random failures of equipment, that is not an issue. But if you have a bad actor at play in which one of the systems involved is compromised, it becomes a big problem.

 

What manual are we talking about? Can you give us a link so we can help you answer your question?

I have no idea how polynomial division relates to your specific system and the way it makes decisions. If you can multiply two polynomials together and get a polynomial, then you should be able to divide one polynomial by another and get a polynomial so long as the divisor is not identically 0.

The manual is from Alstom Signaling which manufactured the automatic train control system. I might be able to provide a link to the PDF containing a description of the controller and general theory of operation.

 

That would be great.
http://en.wikipedia.org/wiki/Cyclic_redundancy_check

 

I believe your on the right track.

Now what I would like to know what is a Boolean polynomial and how can it be divided or multiplied by another Boolean expression.

 

I believe your on the right track.

Now what I would like to know what is a Boolean polynomial and how can it be divided or multiplied by another Boolean expression.

First off, do you know how to divide one "normal" polynomial by another?

For instance, what is

\(
\frac{2x^4 + 12x^3 - 9x + 7}{5x^2 - 17x + 11}
\)

 

Pardon me for giving an prefabricated example just swiped from the net, but here it is:

http://en.wikipedia.org/wiki/Polynomial_long_division

 

Pardon me for giving an prefabricated example just swiped from the net, but here it is:

http://en.wikipedia.org/wiki/Polynomial_long_division

I didn't ask if you could find a link to something written by someone out there that knows polynomial division. I asked if YOU knew what polynomial division is and how to do it.

Unless YOU know how to do regular polynomial division, you don't stand much of a chance at understanding Boolean polynomial division. That's like someone asking how to multiply two five digit numbers together that hasn't learn how to multiply single digit numbers together yet.

 

I believe your on the right track.

Now what I would like to know what is a Boolean polynomial and how can it be divided or multiplied by another Boolean expression.

Please refer back to post #2, in this thread, where I laid out the basics of boolean polynomials. It leaves me wondering if anybody except WBahn even reads my posts.

 

Please refer back to post #2, in this thread, where I laid out the basics of boolean polynomials. It leaves me wondering if anybody except WBahn even reads my posts.

You gave me the correct path to finding out the mathematical answer. However, my main question is how would these polynomials initially be created and how is their division used in the algorithm for a checked redundant control system.

 

I don't know the answer to how they are created. I've forgotten more mathematics than most people have an opportunity to learn.
The device that is used to create a checkword from a block of data is called a linear feedback shift register, and the generator or divisor polynomial tells you how to construct it.

1. You initalize the shift register to an arbitrary value
2. You shift all the data through it
3. You append the checkword to the block of data

Now if you run the algorithm again, except this time you apply the algorithm to the data plus the checkword, the remainder of the "polynomial division" is zero. In the words of Inigo Montoya "..there is too much. Let me sum up".

1. The block of data is the dividend
2. The generator polynomial is the divisor
3. The checkword is the remainder of the division, of the dividend (messgae) polynomial by the divisor (generator) polynomial
4. When the checkword is appended to the original dividend and the algorithm is repeated the remainder of the polynomial division is zero

In your particular application if all three PLCs have a block of "decision data" they each compute the polynomial division checkword and send it off somewhere. If they all compute the same checkword then is is presumed that they all have the same data with a probability close to 1. The reason it is not completely certain is that many different data blocks will compute the same checkword. The question is how different they have to be for that to happen. What is known is that they are very good at detecting burst errors of up to a certain length. This property is used extensively in disk drives and communication systems.

The table in this article describes a large number of those in use:
http://en.wikipedia.org/wiki/Cyclic_redundancy_check
Maybe yours is one of them.

 

You gave me the correct path to finding out the mathematical answer. However, my main question is how would these polynomials initially be created and how is their division used in the algorithm for a checked redundant control system.

The design of divisor polynomials is both an art and a science, like most of engineering. The first thing you have to do is determine what the goal of the system is as there are many factors that play against each other and the performance against one usually has to be traded off to get performance against another. So if you primarily interested in detecting burst errors you do one thing while if you are primarily interested in detecting all errors of less than n-bits you do something else while if you are interested in doing the checksum on very large blocks you do something else while if you are interested in minimizing the collision probabilities you do yet something else. There are some general guidelines regarding what properties the polynomial has to have to give good performance against the various metrics, but often they are found by exhaustively searching a portion of the potential space of all polynomials and testing them against the desired metrics. There are catalogs of polynomials and what their characteristics are.

 

The choice of polynomial is derived from the properties of linear feedback shift registers:

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

For a given word length, only certain polynomials will provide a maximum length random number sequence.

For example, for a 15-bit shift register, the polynomial:

will give a maximum length of 32767.