Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How to construct examples (describe all) polynoms f,g such that for any polynom p(x) not equal to zero: |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms (=Hamming weight, by the way it is norm on the polynomial algebra).

I am mainly interested in the case of polynoms over F_2.

The difficulty is that if we take just one polynom f(x) we can find p(x) such that fp=x^N-1 (see answer to this quest) so |fp|=2 - small. But if we take 2 this trick will not work.

I think that random polynoms will satisfy this property.

Example of such polynoms is given here Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ?

Same argument also works for f = x^n+1; g = x^n +x^k+1.

A bit modification allows to prove for f=x^n+x^l+1; g=x^n+x^k+1.

Here is example which violate this property:

f= x^N + x^3 + x^2+x+1; g=x^N + x^4 + x^3 + x^2+x+1 , N>=6

p(x)=x+1 will give contradiction.

Such polynoms generate "good" convolutional codes. See Given g1(x), g2(x) minimize over p(x) Hamming weight of [p(x)g1; p(x)g2(x) ] ? (Or how to find minimal distance of convolutional code?)

The same can be asked about triples and n-tuples of polynoms.

By the way is the any easy way to see that polynoms:

% The octal representation of the polynomials are

G4 = 133; % 1+D^2+D^3+D^5+D^6

G7 = 171; % 1+D+D^2+D^3+D^6

G5 = 145; % 1+D+D^4+D^6

Satisfy this property ? These polynoms used in some part of GSM.

From MatLab demo file:

%% EGPRS2 Background

% The 3GPP standard introduced General Packet Radio Service (GPRS) to

% support packet switched wireless data transmission over GSM networks.

% The Enhanced GPRS (EGPRS Phase 1) specifications increased the data rates

% by using 8-PSK modulation. In 2007, with the introduction of EGPRS Phase

% 2 (EGPRS2) even higher data rates are achieved through the use of higher

% modulation schemes such as 16- and 32-QAM. EGPRS2 Level B also

% introduced an increased symbol rate of 325 kSps as opposed to the legacy

% symbol rate of 270,833 kSps [ <#25 2> ]. In this demo, we focus on the

% UBS-7 channel, which provides 44.8 kbps data rate [ <#25 4> ]. We assume

% that PAN [ <#25 4> ] is not included in the data. Some key system

% parameters are as follows [ <#25 2>, <#25 4> ]:

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.