/shared/development/google_code/rssoft/library/lib/GFq_Polynomial.h

Go to the documentation of this file.

/*
     Copyright 2013 Edouard Griffiths <f4exb at free dot fr>

     This file is part of RSSoft. A Reed-Solomon Soft Decoding library

     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
     the Free Software Foundation; either version 2 of the License, or
     (at your option) any later version.

     This program is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     GNU General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with this program; if not, write to the Free Software
     Foundation, Inc., 51 Franklin Street, Boston, MA  02110-1301  USA

         Original from Arash Partow (see original copytight notice).
         Extensively modified augmented with a few methods and included in
         RSSoft in gf sub-namespace.

         Univariate polynomials with coefficients in GF(2^m) class hence
         members of GF(2^m)[X]

*/
/*
 *********************************************************************
 *                                                                   *
 *        Galois Field Arithmetic Library (version 0.0.1)            *
 *                                                                   *
 * Class: Galois Field Polynomial                                    *
 * Version: 0.0.1                                                    *
 * Author: Arash Partow - 2000                                       *
 * URL: http://www.partow.net/projects/galois/index.html             *
 *                                                                   *
 * Copyright Notice:                                                 *
 * Free use of this library is permitted under the guidelines and    *
 * in accordance with the most current version of the Common Public  *
 * License.                                                          *
 * http://www.opensource.org/licenses/cpl.php                        *
 *                                                                   *
 *********************************************************************
 */

#ifndef __GFQ_POLYNOMIAL_H__
#define __GFQ_POLYNOMIAL_H__

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <assert.h>
#include "GFq.h"
#include "GFq_Element.h"

namespace rssoft
{
namespace gf
{

class GFq_Polynomial
{

public:

        GFq_Polynomial(const GFq& _gf);

        GFq_Polynomial(const GFq& _gf, const unsigned int size, GFq_Element* gfe = NULL);

        GFq_Polynomial(const GFq& _gf, const std::vector<GFq_Element>& gfe);

        GFq_Polynomial(const GFq_Polynomial& polynomial);

        GFq_Polynomial(const GFq_Element& gfe);

        ~GFq_Polynomial()
        {
        }
        ;

        void init(const std::vector<GFq_Element>& _poly);

        bool is_valid() const;

        bool is_zero() const;

        bool is_one() const;

        unsigned int deg() const;

        const GFq& field() const;

        const std::vector<GFq_Element>& get_poly() const;

        std::vector<GFq_Element>& get_poly_for_update();

    void get_poly_symbols(std::vector<GFq_Symbol>& symbols, unsigned int size=0) const
    {
        symbols.resize((size == 0 ? poly.size() : size));
        std::transform(poly.begin(), poly.end(), symbols.begin(), gfq_element_to_symbol);
    }

        void set_degree(const unsigned int& x);

        GFq_Polynomial& operator =(const GFq_Polynomial& polynomial);
        GFq_Polynomial& operator =(const GFq_Element& gfe);
        GFq_Polynomial& operator+=(const GFq_Polynomial& polynomial);
        GFq_Polynomial& operator+=(const GFq_Element& gfe);
        GFq_Polynomial& operator-=(const GFq_Polynomial& polynomial);
        GFq_Polynomial& operator-=(const GFq_Element& gfe);
        GFq_Polynomial& operator*=(const GFq_Polynomial& polynomial);
        GFq_Polynomial& operator*=(const GFq_Element& gfe);
        GFq_Polynomial& operator/=(const GFq_Polynomial& divisor);
        GFq_Polynomial& operator/=(const GFq_Element& gfe);
        GFq_Polynomial& operator%=(const GFq_Polynomial& divisor);
        GFq_Polynomial& operator%=(const unsigned int& power);
        GFq_Polynomial& operator^=(const int& n);
        GFq_Polynomial& operator<<=(const unsigned int& n);
        GFq_Polynomial& operator>>=(const unsigned int& n);

        GFq_Element& operator[](const unsigned int& term);
        GFq_Element operator()(const GFq_Element& value);
        GFq_Element operator()(GFq_Symbol value);

        const GFq_Element& operator[](const unsigned int& term) const;
        const GFq_Element operator()(const GFq_Element& value) const;
        const GFq_Element operator()(GFq_Symbol value) const;

        bool operator==(const GFq_Polynomial& polynomial) const;
        bool operator!=(const GFq_Polynomial& polynomial) const;

        GFq_Polynomial derivative();
    
    GFq_Element make_monic();

     void rootChien(std::vector<GFq_Element>& roots);

        void set_alpha_format(bool _alpha_format)
        {
                alpha_format = _alpha_format;
        }

        friend std::ostream& operator <<(std::ostream& os, const GFq_Polynomial& polynomial);

protected:
        const GFq& gf; 
        std::vector<GFq_Element> poly; 
        bool alpha_format; // true: power of alpha representation, false: binary representation of printed coefficients
};

void simplify(GFq_Polynomial& polynomial);
GFq_Polynomial operator +(const GFq_Polynomial& a, const GFq_Polynomial& b);
GFq_Polynomial operator +(const GFq_Polynomial& a, const GFq_Element& b);
GFq_Polynomial operator +(const GFq_Element& a, const GFq_Polynomial& b);
GFq_Polynomial operator +(const GFq_Polynomial& a, const GFq_Symbol& b);
GFq_Polynomial operator +(const GFq_Symbol& a, const GFq_Polynomial& b);
GFq_Polynomial operator -(const GFq_Polynomial& a, const GFq_Polynomial& b);
GFq_Polynomial operator -(const GFq_Polynomial& a, const GFq_Element& b);
GFq_Polynomial operator -(const GFq_Element& a, const GFq_Polynomial& b);
GFq_Polynomial operator -(const GFq_Polynomial& a, const GFq_Symbol& b);
GFq_Polynomial operator -(const GFq_Symbol& a, const GFq_Polynomial& b);
GFq_Polynomial operator *(const GFq_Polynomial& a, const GFq_Polynomial& b);
GFq_Polynomial operator *(const GFq_Element& a, const GFq_Polynomial& b);
GFq_Polynomial operator *(const GFq_Polynomial& a, const GFq_Element& b);
GFq_Polynomial operator /(const GFq_Polynomial& a, const GFq_Polynomial& b);
GFq_Polynomial operator /(const GFq_Polynomial& a, const GFq_Element& b);
GFq_Polynomial operator %(const GFq_Polynomial& a, const GFq_Polynomial& b);
GFq_Polynomial operator %(const GFq_Polynomial& a, const unsigned int& power);
GFq_Polynomial operator ^(const GFq_Polynomial& a, const int& n);

GFq_Polynomial operator <<(const GFq_Polynomial& a, const unsigned int& n);

GFq_Polynomial operator >>(const GFq_Polynomial& a, const unsigned int& n);

GFq_Polynomial gcd(const GFq_Polynomial& a, const GFq_Polynomial& b);

std::pair<GFq_Polynomial, GFq_Polynomial> div(const GFq_Polynomial& a,
                const GFq_Polynomial& b);

std::vector<GFq_Element> rootex_nz(const GFq_Polynomial& a);

std::vector<GFq_Element> rootex(const GFq_Polynomial& a);

GFq_Polynomial get_monic(const GFq_Polynomial& a, GFq_Element& lead_poly);

std::vector<GFq_Polynomial> square_free_decomposition(const GFq_Polynomial& a);

} // namespace gf
} // namespace rssoft

#endif // __GFQ_POLYNOMIAL_H__