Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By emakarov

Thread: Proof of commutativity and associativity for binary error pattern

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    308
    Thanks
    16

    Proof of commutativity and associativity for binary error pattern

    There's a math problem on page-34 of Pinter's "A Book of Abstract Algebra" book which is(Problem F):

    If a word is $\displaystyle \mathbf{a} = a_1 a_2 \cdots a_n$ is sent, but a word $\displaystyle \mathbf{b} = b_1 b_2 \cdots b_n$ is received(where the $\displaystyle a_i$
    and $\displaystyle b_j$ are $\displaystyle 0s$ or $\displaystyle 1s$), then the error pattern is the word $\displaystyle e = e_1 e_2 ... e_n$ where:

    $\displaystyle e_i = \begin{cases} 0 & \text{ if } a_i = b_i \\ 1 & \text{ if } a_i \neq b_i \end{cases}$

    With this motivation, we define an operation of adding words, as follows: If $\displaystyle \mathbf{a}$ and $\displaystyle \mathbf{b}$ are both of length
    $\displaystyle 1$, we add them according to the rules

    $\displaystyle 0 + 0 = 0$, $\displaystyle 1 + 1 = 0$, $\displaystyle 0 + 1 = 1$ and $\displaystyle 1 + 0 = 1$


    If $\displaystyle \mathbf{a}$ and $\displaystyle \mathbf{b}$ are both of length $\displaystyle n$, we add them by adding corresponding digits. That is(let us
    introduce commas for convenience),

    $\displaystyle (a_1, a_2, \cdots, a_n) + (b_1, b_2, \cdots, b_n) = (a_1 + b_1, a_2 + b_2, \cdots, a_n + b_n)$


    Thus the sum of $\displaystyle \mathbf{a}$ and $\displaystyle \mathbf{b}$ is the error pattern $\displaystyle \mathbf{e}$.

    For example,

    $\displaystyle 0010110 + 0011010 = 0001100$ and $\displaystyle 10100111 + 11110111 = 01010000$

    The symbol $\displaystyle \mathbb{B}^n$ will designate the set of all the binary words of length $\displaystyle n$.

    We will prove that the operation of word addition has the following properties on $\displaystyle \mathbb{B}^n$:


    1. It is commutative.
    2. It is associative.
    3. There is an identity element for word addition.
    4. Every word has an inverse under word addition.


    .....

    1) Show that

    $\displaystyle (a_1, a_2, \cdots, a_n) + (b_1, b_2, \cdots b_n) = (b_1, b_2, \cdots, b_n) + (a_1, a_2, \cdots, a_n)$

    3) Show that

    $\displaystyle \begin{align*}(a_1, a_2, \cdots, a_n) + [(b_1, b_2, \cdots, b_n) + (c_1, c_2, \cdots, c_n)] =& [ (a_1, a_2, \cdots, a_n) + (b_1, b_2, \cdots, b_n) ] \\ + & (c_1, c_2, \cdots, c_n) \end{align*}$.


    How can I prove that the commutativity and associativity holds in this case?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Proof of commutativity and associativity for binary error pattern

    For each digit, this is addition modulo 2. It;s a well-known fact that addition modulo n is commutative and associative.
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    308
    Thanks
    16

    Re: Proof of commutativity and associativity for binary error pattern

    Quote Originally Posted by emakarov View Post
    For each digit, this is addition modulo 2. It;s a well-known fact that addition modulo n is commutative and associative.
    Thanks emakarov for help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary Integer Proof?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 04:22 AM
  2. Replies: 6
    Last Post: Apr 26th 2011, 01:58 PM
  3. probability to create a binary bit pattern
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Feb 24th 2010, 01:59 PM
  4. Associativity Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 18th 2009, 08:47 AM
  5. Absolute and Relative error of 3/11 (Binary form)
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: Mar 8th 2009, 08:30 AM

Search Tags


/mathhelpforum @mathhelpforum