2
$\begingroup$

i'm reading the article of J. L. Massey and M. K. Sain, "Inverses of Linear Sequential Circuits" (Date of Publication - April 1968) (here) and i cannot understand - what is "feedforward inversion"?

They give a short description of circles in convolution codes and a little bit description about catastrophic codes (codes that makes an infinite amount of errors on decoding if there was a couple of errors in channel).

Can anyone explain the term "feedforward inversion", and what do they mean by delay in that regard?

P.S. i'm interested in this theme because i want to understand the proof of Theorem 1 in that article, no more.

$\endgroup$
1
$\begingroup$

The paper deals with sequential encoding and decoding of codes. Maybe you have heard of "block codes": these codes take a message $M\in \{0,1\}^k$, perform some computation, and then output a code-word $c_M \in \{0,1\}^n$.(1). A main drawback of encoding systems for such codes is that need to know the entire message $M$ in order to output $c_M$.

This is not the case in convolution code.

Sequential circuits

Convolution codes are usually designed so that there is a very simple and sequential encoding algorithm. By "sequential" I mean that the system reads $M$ bit by bit, and immediately(2) outputs some part of $c_M$. Say, if the rate is $k/n=1/2$, then for every bit of $M$ given as an input to the encoder, the encoding system outputs the next $2$ bits of the codeword (even without knowing the rest of $M$). After the entire input $M$ is fed into the encoder, we will get the entire codeword $c_M$.

This sequential nature of encoding is what the paper means by "feed-forward": you always input the next part of the data, and that's enough for the system to proceed and give output, as a function on the current state of the encoder. This is/was crucial in memoryless implementations (those can't hold the past bits of the message $M$), or implementations that could not wait to have the entire $M$ due to the large delay incurred (those don't know the future bits of the message $M$).

Thus, a "feedforward inverse" is simply a sequential decoding algorithm. ("inverse" is the algorithm that inverses the code, that is, the decoding system).

Delay

The delay $L$ is explained in the first paragraph of the paper: (below, not a precise quote)

An inverse with delay $L$, for a sequential circuit with $k$ inputs and $n$ outputs [= a decoder for the encoder], is a sequential circuit with $n$ inputs and $k$ outputs, that cascaded with the encoder, yields an overall sequential circuit with delay $L$.

That is, take the encoder, and connect the decoder immediately to the output of the encoder. Now start feeding the input into the encoder. $L$ is the amount of "clocks" until you see the same bit at the output of the decoder.


(1) The alphabet needs not be binary, this is just for simplicity.

(2) Or after a fixed number of clocks.

$\endgroup$
  • $\begingroup$ wow. now it is much more clear ;) well, when i was reading this paper, i meant under convolution coder something like this c2n.me/3jeYppX ( the (+) is XOR, isn't it? ) and i really didn't got, what is the "delay" was meant, because by default i filled those "boxes" with zeros, so, for example, if i'll feed a 111...111 sequence to this coder, i'll get (by codewords for every information bit): 10 11 00 00 00 00 ... so i really didn't got, what is "delay". now it is clear, thank You! $\endgroup$ – esselesse Jun 13 '15 at 20:31
  • $\begingroup$ the another point is - i know another interpretation of that theorem, it sounds like "The code is NOT catastrophic (i.e. the code that makes finite-weightened code for infinite-weightened input vector) when and only when GCD of determinants of all submatrixes (k x k) of G (k is one of parameters of code, (n, k, d)) is = x**s, where s≥0", so i don't understand, is it the same theorem or not... =( $\endgroup$ – esselesse Jun 13 '15 at 20:42
  • $\begingroup$ Thank you. I'm not familiar enough with that paper to answer your other question. $\endgroup$ – Ran G. Jun 13 '15 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.