Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences (Q841240)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences
scientific article

    Statements

    Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences (English)
    0 references
    0 references
    0 references
    0 references
    15 September 2009
    0 references
    Let \(g_1,\dots,g_s\in{\mathbb F}_q\) be arbitrary monic polynomials each of degree at least one. Let \({\mathcal M}(g_1,\dots,g_s)\) denote the set of \(s\)-fold multisequences \((\sigma_1,\dots,\sigma_s)\) such that \(\sigma_i\) is a linear recurring sequence over \({\mathbb F}_q\) with characteristic polynomial \(g_i\) for each \(1\leq i\leq s\). Let \(\Phi(d;g_1,\dots,g_s)\) denote the number of multisequences from \({\mathcal M}(g_1,\dots,g_s)\) with joint minimal polynomial \(d\in{\mathbb F}_q\). The main results of the paper give a formula for the counting function \(\Phi(d;g_1,\dots,g_s)\) and the expectation and the variance of the joint linear complexity of random multisequences that are uniformly distributed over \({\mathcal M}(g_1,\dots,g_s)\), where \(g\)'s are arbitrary nonconstant monic polynomials over \({\mathbb F}_q\) all in terms of parameters involving the factorizations of \(g_1,\dots,g_s\) and \(d\).
    0 references
    joint linear complexity
    0 references
    random multisequences
    0 references
    linear recurring sequences
    0 references
    expectation
    0 references
    variance
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references