

A007227


Number of distinct perforation patterns for deriving (v,b) = (n+2,n) punctured convolutional codes from (3,1).
(Formerly M4624)


2



9, 42, 236, 1287, 7314, 41990, 245256, 1448655, 8649823, 52106040, 316360752, 1933910820, 11893566078, 73537906926, 456864894288, 2850557192175, 17854854154215, 112230508880490, 707714010205020, 4475876883386895
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,1


COMMENTS

"A punctured convolutional code is a highrate code obtained by the periodic elimination (i.e., puncturing) of specific code symbols from the output of a lowrate encoder. The resulting highrate code depends on both the lowrate code, called the original code, and the number and specific positions of the punctured symbols." (The quote is from Haccoun and Bégin (1989).)
A highrate code (v,b) (written as R = b/v) can be constructed from a lowrate code (v0,1) (written as R = 1/v0) by deleting from every v0*b code symbols a number of v0*b  v symbols (so that the resulting rate is R = b/v).
Even though the formulas below do not appear in the two published papers in the IEEE Transactions on Communications, from the theory in those two papers, it makes sense to replace "kb" with "kv0*b" (and "kgcd(v,b)" with "kgcd(v,v0*b)"). Pab Ter, however, uses "kb" in the Maple program below. (End)


REFERENCES

Guy Bégin, On the enumeration of perforation patterns for punctured convolutional codes, Séries Formelles et Combinatoire Algébrique, 4th colloquium, 1519 Juin 1992, Montréal, Université du Québec à Montréal, pp. 110.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA

The number of perforation patterns to derive highrate convolutional code (v,b) (written as R = b/v) from a given lowrate convolutional code (v0, 1) (written as R = 1/v0) is (1/b)*Sum_{kgcd(v,b)} phi(k)*binomial(v0*b/k, v/k).
According to Pab Ter's Maple code, this is the coefficient of z^v in the polynomial (1/b)*Sum_{kb} phi(k)*(1 + z^k)^(v0*b/k).
Here (v,b) = (n+2,n) and (v0,1) = (3,1), so
a(n) = (1/n)*Sum_{kgcd(n+2,n)} phi(k)*binomial(3*n/k, (n+2)/k).
This simplifies to
a(n) = (1/n)*(binomial(3*n, n+2) + [(n mod 2) = 0]*binomial(3*n/2, (n/2) + 1)), where [ ] is the Iverson bracket. (End)


MAPLE

with(numtheory):P:=proc(b, v0) local k: RETURN(add(phi(k)*(1+z^k)^(v0*(b/k)), k=divisors(b))/b): end; seq(coeff(P(b, 3), z, b+2), b=2..40); (Pab Ter)


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005


STATUS

approved



