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

Math Help - Proof of commutativity and associativity for binary error pattern

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    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 \mathbf{a} = a_1 a_2 \cdots a_n is sent, but a word \mathbf{b} = b_1 b_2 \cdots b_n is received(where the a_i
    and b_j are 0s or 1s), then the error pattern is the word e = e_1 e_2 ... e_n where:

    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 \mathbf{a} and \mathbf{b} are both of length
    1, we add them according to the rules

    0 + 0 = 0, 1 + 1 = 0, 0 + 1 = 1 and 1 + 0 = 1


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

    (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 \mathbf{a} and \mathbf{b} is the error pattern \mathbf{e}.

    For example,

    0010110 + 0011010 = 0001100 and 10100111 + 11110111 = 01010000

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

    We will prove that the operation of word addition has the following properties on \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

     (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

    \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,559
    Thanks
    785

    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
    300
    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, 05:22 AM
  2. Replies: 6
    Last Post: April 26th 2011, 02:58 PM
  3. probability to create a binary bit pattern
    Posted in the Statistics Forum
    Replies: 3
    Last Post: February 24th 2010, 02:59 PM
  4. Associativity Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 18th 2009, 09:47 AM
  5. Absolute and Relative error of 3/11 (Binary form)
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: March 8th 2009, 09:30 AM

Search Tags


/mathhelpforum @mathhelpforum