---
title: "Decimation"
canonical: "https://docs.magma-maths.org/CodingTheory/PseudoRandomBitSequences/misc.html"
source: "https://docs.magma-maths.org/CodingTheory/PseudoRandomBitSequences/misc.md"
part: "Coding Theory"
chapter: "Pseudo-Random Bit Sequences"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "../../index.md"}
  - {"title": "Coding Theory", "source": "../index-coding-theory.md"}
  - {"title": "Pseudo-Random Bit Sequences", "source": "index-pseudo-random-bit-sequences.md"}
prev: {"title": "Correlation Functions", "source": "correlation.md"}
next: {"title": "Hash Functions", "source": "hash.md"}
intrinsics:
  - {"name": "Decimation", "signature": "Decimation(S, f, d): SeqEnum, RngIntElt, RngIntElt -> SeqEnum"}
  - {"name": "Decimation", "signature": "Decimation(S, f, d, t): SeqEnum, RngIntElt, RngIntElt, RngIntElt -> SeqEnum"}
examples:
  - "ex-29a760"
---

# Decimation

<a id="function-decimation-seqenum-rngintelt-rngintelt"></a>
## `Decimation(S, f, d): SeqEnum, RngIntElt, RngIntElt -> SeqEnum`

Given a binary sequence $S$, and integers $f$ and $d$, return the decimation of $S$. This is the sequence containing elements $S[f]$, $S[f+d]$, $S[f+2d]$, … where the indices in $S$ are interpreted with wrap-around as integers between $1$ and $\#S$.

<a id="function-decimation-seqenum-rngintelt-rngintelt-rngintelt"></a>
## `Decimation(S, f, d, t): SeqEnum, RngIntElt, RngIntElt, RngIntElt -> SeqEnum`

Decimation of the sequence $S$. Returns a new sequence containing the first $t$ elements of $S[f]$, $S[f+d]$, $S[f+2d]$, … where the indices in $S$ are interpreted with wrap-around as integers between $1$ and #$S$.

<a id="example-ex-29a760"></a>
## `Example: Decimating an LFSR Sequence (ex-29a760)`

Given a primitive polynomial over ${\bf F}_{q}$, one can obtain another primitive polynomial by decimating an LFSR sequence obtained from the initial polynomial. This is demonstrated in the code below.

```magma
> K := GF(7);
> C<D> := PrimitivePolynomial(K, 2);
> C;
D^2 + 6*D + 3
```

In order to generate an LFSR sequence, we must first multiply this polynomial by a suitable constant so that the trailing coefficient becomes $1$.

```magma
> C := C * Coefficient(C,0)^-1;
> C;
5*D^2 + 2*D + 1
```

We are now able to generate an LFSR sequence of length $7^2 - 1$. The initial state can be anything other than $[0, 0]$.

```magma
> t := LFSRSequence (C, [K| 1,1], 48);
> t;
[ 1, 1, 0, 2, 3, 5, 3, 4, 5, 5, 0, 3, 1, 4, 1, 6, 4, 4, 0, 1, 5, 6, 5, 2, 6, 6,
0, 5, 4, 2, 4, 3, 2, 2, 0, 4, 6, 3, 6, 1, 3, 3, 0, 6, 2, 1, 2, 5 ]
```

We decimate the sequence by a value $d$ having the property $\gcd(d,48)=1$.

```magma
> t := Decimation(t, 1, 5);
> t;
[ 1, 5, 0, 6, 5, 6, 4, 4, 3, 1, 0, 4, 1, 4, 5, 5, 2, 3, 0, 5, 3, 5, 1, 1, 6, 2,
0, 1, 2, 1, 3, 3, 4, 6, 0, 3, 6, 3, 2, 2, 5, 4, 0, 2, 4, 2, 6, 6 ]
> B := BerlekampMassey(t);
> B;
3*D^2 + 5*D + 1
```

To get the corresponding primitive polynomial, we multiply by a constant to make it monic.

```magma
> B := B * Coefficient(B, 2)^-1;
> B;
D^2 + 4*D + 5
> IsPrimitive(B);
true
```