PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very low Entry average rating: No information on entry rating
weight enumerator (Definition)

Let $ A$ be an alphabet and $ C$ a finite subset of $ A^*$. Then the complete weight enumerator of $ C$, denoted by $ {\mathrm{cwe}}_C$, is the polynomial in $ \vert A\vert$ indeterminates $ X_a$ labeled by the letters of $ a\in A$ with integer coefficients defined by

$\displaystyle {\mathrm{cwe}}_C((X_a)_{a\in A}):=\sum\limits _{c\in C}\prod\limits _{a\in A}X_a^{{\mathrm{wt}}_a(c)},$    

where $ {\mathrm{wt}}_a(c)$ is the $ a$-weight of the string $ c$.

If $ A$ is an abelian group, one defines the Hamming weight enumerator of $ C$, denoted by $ {\mathrm{we}}_C$, as a polynomial in only two indeterminates $ X$ and $ Y$:

$\displaystyle {\mathrm{we}}_C(X,Y):={\mathrm{cwe}}_C((X_a)_{a\in A})\vert_{\begin{array}{l}\scriptstyle X_0=X\\ \scriptstyle X_a=Y\text{ if }a\neq 0\end{array}},$    

that is one distinguishes only between zero and the non-zero letters of the strings in $ C$.

If $ C$ is a code of block length $ n$, then both $ {\mathrm{cwe}}_C$ and $ {\mathrm{we}}_C$ are homogeneous of degree $ n$. Therefore, one can set $ Y=1$ in $ {\mathrm{we}}_C$ in this case without losing information. The resulting polynomial can be uniquely rewritten in the form

$\displaystyle {\mathrm{we}}_C(X,1)=\sum\limits _{i=0}^nA_iX^{n-i},$    

the sequence $ A_0,\ldots A_n$ defining the Hamming weight distribution. Analogously, one can define more general weight distributions by setting all but one indeterminate in $ {\mathrm{cwe}}_C((X_a)_{a\in A})$ equal to one.

Examples

  • Let $ C$ be the ternary (that is $ A=\mathbb{F}_3=\{0,1,2\}$) linear code of block length $ 4$ spanned by the vectors $ (1,1,1,1)$, $ (1,1,0,0)$ and $ (1,0,1,0)$. Then
    $\displaystyle {\mathrm{cwe}}_C(X_0,X_1,X_2)=X_0^4+4X_0^2X_1^2+4X_0^2X_1X_2+4X_0^2X_2^2+4X_0X_1^2X_2+4X_0X_1X_2^2+X_1^4+4X_1^2X_2^2+X_2^4$    

    and
    $\displaystyle {\mathrm{we}}_C(X,Y)=X^4+12X^2Y^2+8XY^3+6Y^4$    

    and the Hamming weight distribution is $ 1,0,12,8,6$.
  • The Hamming weight enumerator of the full binary code of length $ n$, $ \mathbb{F}_2^n$, is simply given by $ {\mathrm{we}}_{\mathbb{F}_2^n}(X,Y)=(X+Y)^n$, and the Hamming weight distribution is the $ n$-th row of Pascal's triangle.



"weight enumerator" is owned by GrafZahl.
(view preamble)

View style:

See Also: Kleene star, linear code

Other names:  Hamming weight enumerator
Also defines:  complete weight enumerator, weight distribution, Hamming weight distribution
Keywords:  code, linear code, Hamming
Log in to rate this entry.
(view current ratings)

Cross-references: Pascal's triangle, length, binary code, vectors, linear code, sequence, information, block length, code, abelian group, string, coefficients, integer, indeterminates, polynomial, subset, finite, alphabet

This is version 1 of weight enumerator, born on 2005-04-30.
Object id is 6987, canonical name is WeightEnumerator.
Accessed 3032 times total.

Classification:
AMS MSC: 94A55 (Information and communication, circuits :: Communication, information :: Shift register sequences and sequences over finite alphabets)
 94B05 (Information and communication, circuits :: Theory of error-correcting codes and error-detecting codes :: Linear codes, general)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)