; Hamming Code Simulation  
; written by Teresa Carrigan, 2004 


globals [ from-number from-string start-x myDigits praise digits1 save-base base step parity bin-count-list ] 
breeds [ digit arrow check ones] 
arrow-own [ state ]
patches-own [ name column ]


; runs the program when it is first loaded
to startup
  setup
end

to random-setup
  set number-of-digits 2 + random 7
  setup
end


; initializes variables
to setup
  locals [ current n]
  ca
  set praise ["Awesome!" "You got it!" "Right!" "Correct!" "Perfect!" "Bravo!" "Splendid!"]
  set digits1 [ "0" "1" ]
  set base 2
  set save-base base
  set myDigits []  
  set n 0
  set start-x 12
  set parity "even"
  set current 1
  set n 0
  
  repeat 2 [
        set myDigits lput ( item n digits1 ) myDigits
        set n (n + 1)
    ]  
  set n 1
  
  ;  initialize binary number
  set from-number ""
  repeat number-of-digits
    [  set from-number (word from-number (random-one-of myDigits))
    ]
  
; create explanation bar at bottom
  ask patches with [ pycor < -3 ]
    [set pcolor blue]
  ask patch-at 6 -4
    [ set plabel  (word "How should we send "  add-space from-number " using")
      set plabel-color white
      set name 1
    ]
  ask patch-at 6 -5
    [
      set plabel-color white
      set plabel "Hamming code? (even parity, " + number-of-digits + " data bits)"
      set name 2
    ]
  set step 1

  setup-bits from-number
  setup-arrow

end

to step1
  locals [ m r p]
  explain 1 "Determine the number and positions of check bits needed."
  set m 0
  set r 0
  set p 1
  while [ m < number-of-digits ]
    [  set r (r + 1)
       set m ( 2 ^ r) - r - 1
       explain 2 "C" + p + " goes in position " + p + "."
       make-check-bit r p
       set p (2 * p)
       wait slow-motion * 3
    ]
  explain 2 "C" + p + " would go in position " + p + " - no data bits past it."
  wait slow-motion * 6
  explain 2 "So, for " + number-of-digits + " data bits, we need " + r + " check bits."
  set step (step + 1)
end

to make-check-bit [ r p ]
  locals [ here-x here-y where phere-x n]
  set where [0 0 0 -2 -10 ]
  ask max-one-of digit [ xcor ]
    [ set here-x xcor
      set here-y ycor
    ]
  set here-x (here-x + (item r where))
  if any? digit with [ xcor = here-x ]
  [  ask digit with [ xcor <= here-x ]
    [ set heading -90
      fd 1
      wait slow-motion
      fd 1
      wait slow-motion
    ]
    ask min-one-of digit [ xcor]
      [ set phere-x xcor ]
    ask patch-at (phere-x + 2) (here-y + 2)
      [  set n plabel
         set n remove " " n
         set n remove "#" n
      ]
    ask patch-at phere-x (here-y + 2)
        [  set plabel-color cyan
           set n read-from-string n
           set n n + 1
           set plabel "#" + n + " "
        ]
  ]
  cct-check 1
    [  setxy here-x here-y
       set shape "circle"
       set color yellow
       set size 2
       set label "C" + p
       set label-color black
   ]

end

to step2
  locals [ n k ]
  explain 1 "Mark each position with the binary "
  explain 2 "equivalent of the position number."
  set bin-count-list ["0000" "0001" "0010" "0011" "0100" "0101" "0110" "0111" "1000" "1001" "1010" "1011" "1100" ]
  set k 1
  set n count turtles
  while [ k <= n ]
    [ wait slow-motion
      ask patches with [ plabel = "#" + k + " " ]
        [ ask patch-at 0 2
            [  set plabel-color white
               set plabel item k bin-count-list
            ]
         ]
      set k (k + 1)
    ]
  set step (step + 1)
end

to step3
  locals [ n check-set ]
  ask patches with [ plabel-color = cyan ]
    [ set n plabel
      set n remove " " n
      set n remove "#" n
      set n read-from-string n
      set column n
    ]
  explain 1 "C1 checks bits in positions marked ---1."
  set check-set patches with [ column mod 2 = 1 ]
  determine-parity check-set "C1" 
  ask ones [ die ]
  set step step + 1
end

to step4
  locals [ check-set ]
  ifelse any? check with [ label = "C2"]
    [
      explain 1 "C2 checks bits in positions marked --1-."
      set check-set patches with [ member? column [ 2 3 6 7 10 11] ]
      determine-parity check-set "C2" 
      ask ones [ die ]
      set step step + 1
    ]
    [  finish-up
    ]
end

to step5
  locals [ check-set ]
  ifelse any? check with [ label = "C4"]
    [
      explain 1 "C4 checks bits in positions marked -1--."
      set check-set patches with [ member? column [ 4 5 6 7 12 13] ]
      determine-parity check-set "C4" 
      ask ones [ die ]
      set step step + 1
    ]
    [  finish-up
    ]
end

to step6
  locals [ check-set ]
  ifelse any? check with [ label = "C8"]
    [
      explain 1 "C8 checks bits in positions marked 1---."
      set check-set patches with [ column >= 8 ]
      determine-parity check-set "C8" 
      ask ones [ die ]
      set step step + 1
    ]
    [  finish-up
    ]
end

to step7
  finish-up
end

to determine-parity [ check-set ch ]
  locals [ here-parity]
  ask check-set
    [  ask digit-at 0 -2
          [hatch 1
          [  set breed ones
             set shape "circle"
             set color yellow
             set size 2
             set label-color black
          ]
          ]
    ]
  wait slow-motion * 3
  ask ones
    [ set heading 180 
      repeat 4
          [ fd 0.5
            wait slow-motion
          ]
    ]
  explain 2 "Ignore bits that are 0."
  wait slow-motion * 3
  ask ones with [ label = "0 " ]
    [ die ]
  ask arrow
    [ set xcor start-x ]  
   
  while [ count ones with [ color = yellow ] > 0 ]
    [   ask arrow 
        [  showturtle
           ifelse any? other-ones-here
             [  ask other-ones-here
                   [ set color red 
                   ]
                if count ones with [color = red] = 2
                  [ explain 2 "Dropping a pair of ones." 
                    ask ones with [color = red]
                        [ die ]
                    wait slow-motion
                  ]
                fd 1
                wait slow-motion
             ]
             [  explain 2 ""
                fd 1
                wait slow-motion
             ]
        ]      
    ]
  wait slow-motion * 3
  ask arrow
    [ hideturtle ]
  ifelse count ones = 0
    [ set here-parity "even" 
      explain 1 "No ones left, so parity is currently even."
      set-check-bit ch 0
    ]
    [ set here-parity "odd" 
      explain 1 "A one left, so parity is currently odd."
      set-check-bit ch 1
    ]
  wait slow-motion
end

to set-check-bit [ ch x ]
  explain 2 "Setting " + ch + " to " + x + "."
  ask check with [ label = ch ]
    [  set breed digit
       set label x + " "
       set shape "circle"
    ]
end
  
;  read the digits, storing it as a string
to-report get-number 
  locals [ target n num]
  set target ""
  ask max-one-of digit [ xcor ]
      [set n xcor ]
  repeat count digit
        [  set num label-of random-one-of digit with [ xcor = n ]
           set target (word num target)
           set n (n - 2)
        ]

  set target remove " " target
  report target
end


; adds a space in the number so it can be read easier
to-report add-space [ number ]
  locals [ save k ]
  set save ""
  set k 0
  while [ (length number) > 0 ]
    [
      set save (word last number save )
      set number butlast number
      set k (k + 1)
      if (k = 4) and (length number > 0)
        [ set save (word " " save )
          set k 0
        ]
    ]
  set number save  
  report number
end



; this is for the bottom explanation
to explain [ which what ]
  ask patches with [ name = which ]
    [ set plabel what ]
end

; setup the red arrow
to setup-arrow
  locals [here-y ]
  ask random-one-of digit [ set here-y ycor ]
  
  ;  create red arrow
  cct-arrow 1 [
    hideturtle
    setxy start-x ( here-y - 2)
    set heading -90
    set color red
    set shape "arrow"
    set size 2
    set state 0
  ]
end

; setup the bits
to setup-bits [ unsigned ]
  locals [ here-x here-y n ]
  set here-x ( start-x - 2)
  set here-y 1
  set n 1
  repeat number-of-digits
    [
      cct-digit 1
      [ 
        setxy here-x here-y
        set shape "circle"
        set color white
        set size 2
        set label-color black
        set label (word (last unsigned)  " ")
      ] ; end cct digits
      ask patch-at here-x (here-y + 2)
        [  set plabel-color cyan
           set plabel "#" + n + " "
        ]
      set unsigned but-last unsigned
      set here-x (here-x - 2)   
      set n (n + 1)
      wait slow-motion
    ]
  
end



to finish-up
  explain 1 "Original bits = " + add-space from-number + "."
  explain 2 "Hamming encoding = " + add-space get-number + "."
  set step 10
end

; flips the digits (called by the invert procedure)
to flip
  if any? other-digit-here
    [
      ask other-digit-here
        [  set color yellow
            ifelse first label = "0"
              [  set label "1 " ]
              [  set label "0 " ]
        ]
    ]
end


;  do whatever step comes next, then wait until user wants to continue
to one-step
  locals [ which ]
  if step < 10
    [  set which (word "step" step)
       run which
    ]
end


; this is the go button, that when pressed, goes through the entire simulation
to go
  locals [  which-step]
  set which-step "step" + step
  ifelse  step < 10
    [ run which-step
      set which-step "step" + step
      wait slow-motion
    ]
    [  stop
    ]
end

to show-again
  locals [ current n]
  set start-x 12
  set current 1
  
  set n 1
  
  explain 1 (word "How should we send "  add-space from-number " using")
  explain 2 "Hamming code? (even parity, " + number-of-digits + " data bits)"

  set step 1

  ask turtles [ die ]
  ask patches with [ pycor > -3 ]
    [set plabel ""]
  
  setup-bits from-number
  setup-arrow
end

;  ask a quiz question
to quiz
  locals [ save-slow ]
  set save-slow slow-motion
  set slow-motion 0
  without-interruption [random-setup ]
  wait .5
  ask-other
  set slow-motion save-slow
end

to ask-other 
  locals [ guess target question ]
  without-interruption [ set question from-number ]
  set question add-space question
  set guess user-input (word "How should we send " question " using Hamming code?")
  set guess clean-input guess
  set target calc
  ifelse guess = target 
    [ user-message random-one-of praise ]
    [ user-message "I'm sorry, but the correct answer is " + target]
end

to-report clean-input [guess]
  set guess remove " " guess
  set guess remove "," guess
  report guess  
end


to-report calc
  locals [  which-step result]
  set which-step "step" + step
  while  [step < 10]
    [ run which-step
      set which-step "step" + step
    ]
  set result clean-input get-number
  report result
end


; *** NetLogo Model Copyright Notice ***
;
; Copyright 2004 by Teresa W. Carrigan.  All rights reserved.
;
; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
;    from Teresa W. Carrigan.
; Contact Teresa W. Carrigan for appropriate licenses for redistribution 
; for profit.
;
; To refer to this model in academic publications, please use:
; Carrigan, T. (2004).  Hamming Code Simulation 
; Blackburn College, Carlinville, IL.
;
; In other publications, please use:
; Copyright 2004 by Teresa W. Carrigan.  All rights reserved.  
;
; *** End of NetLogo Model Copyright Notice ***
@#$#@#$#@
GRAPHICS-WINDOW
13
10
698
316
13
5
25.0
1
18
1
1
1

CC-WINDOW
27
459
564
629
Command Center

BUTTON
13
318
76
351
NIL
setup
NIL
1
T
OBSERVER
T

SLIDER
257
319
429
352
slow-motion
slow-motion
0
1
0.3
0.1
1
NIL

BUTTON
13
351
76
384
step
one-step
NIL
1
T
OBSERVER
T

BUTTON
77
352
140
385
NIL
go
T
1
T
OBSERVER
T

SLIDER
433
320
605
353
number-of-digits
number-of-digits
1
8
4
1
1
bits

BUTTON
77
317
140
350
random
random-setup
NIL
1
T
OBSERVER
T

BUTTON
143
318
241
351
NIL
show-again
NIL
1
T
OBSERVER
T

BUTTON
144
352
240
385
NIL
quiz
NIL
1
T
OBSERVER
T

@#$#@#$#@
WHAT IS IT?
-----------
This model demonstrates storing of bit patterns using Hamming SEC, even parity, with up to eight data bits. 

HOW IT WORKS
------------
First a random bit pattern is generated, of the length specified by the number-of-digits slider.  Extra bits known as check bits are added so that they occupy positions 1, 2, 4, and 8.  If there will be no data bits past a check bit, then that check bit is not needed.  

Each position is then marked with the binary equivalent of the position number.  This will help us determine easily which bits are checked by which check bit.  Each check bit has a single one in the binary equivalent of its position number, and checks all bits that have a one in that same place in the binary equivalent.  Each check bit will force its own group to have even parity.  

HOW TO USE IT
-------------
The setup button generates a random bit pattern, of the length specified by the number-of-digits slider.

The random button generates a random number of bits, and then uses that to generate a random bit pattern.

The step button demonstrates the next step, and then stops so you can take notes.  This is useful when you are first learning the method.

The go button does every remaining step, at a speed determined by the slow-motion slider.  This is useful when you do not need to take notes between each step.

The show-again button starts the exact problem from the beginning.  You may then click either the step button or the go button to see the same demonstration.

The quiz button will generate a random problem.  Spaces and commas in your answer will be removed, so feel free to use them to help you count the digits.  

The slow-motion slider is an easy way to adjust the speed of the display.  Set it to zero if you want to show the final result as quickly as possible.  0.3 is a good setting for most purposes.

The number-of-digits slider determines the number of data bits to be generated when the setup button is pressed.


THINGS TO NOTICE
----------------
After the first two check bits, each additional check bit allows at least double the number of data bits before another check bit is required.

Although there are numerical methods for determining the number of check bits needed, we know that the check bits always go in positions that are powers of two, and if there are no data bits past a check bit position, that check bit is not needed.  This gives us an easy way to determine the number of check bits needed.

The group of bits checked by a check bit is easily determined by looking at the binary equivalent of the position number.  Each bit in that group will have a 1 in the same place.

THINGS TO TRY
-------------
Set slow-motion to 0.3, click random, and then click go.

Set the number-of-digits slider to the number of data bits you wish to drill, and click setup.  Work each step by hand, and then click the step button to check your answer.

EXTENDING THE MODEL
-------------------
Allow the user to input the starting bit pattern.

Allow for more than eight data bits.

Modify the model to use a Hamming double-error-correcting code.

NETLOGO FEATURES
----------------
one-step uses the NetLogo run command combined with a global integer variable step to run the next step, without needing nested ifelse blocks. 

The arrow uses "other-BREED-here" to interact with the yellow bits.


RELATED MODELS
--------------
Parity Simulation, Hamming Error Detection


CREDITS AND REFERENCES
----------------------
This model was written by Teresa W. Carrigan, 2004.  

Permission to use, modify or redistribute this model is hereby granted,
provided that both of the following requirements are followed:
	a) this copyright notice is included.
	b) this model will not be redistributed for profit without permission
	   from Teresa W. Carrigan.
Contact Teresa W. Carrigan for appropriate licenses for redistribution 
for profit.

To refer to this model in academic publications, please use: 
Carrigan, T. (2004). Hamming Code Simulation 
Blackburn College, Carlinville, IL.

In other publications, please use: 
Copyright 2004 by Teresa W. Carrigan.  All rights reserved.  

FOR MORE INFORMATION
--------------------
For more information on Hamming Codes, see one of the following textbooks:
[1] Null, L. and Lobur, J. "Essentials of Computer Organization and Architecture", First Edition. Jones and Bartlett. pages 77-82. 
[2] Murdocca, M. and Heuring, V. "Principles of Computer Architecture", First Edition. Prentice Hall, pages 359-365.

@#$#@#$#@
default
true
0
Polygon -7566196 true true 150 5 40 250 150 205 260 250

arrow
true
0
Polygon -7566196 true true 150 0 0 150 105 150 105 293 195 293 195 150 300 150

box
true
0
Polygon -7566196 true true 45 255 255 255 255 45 45 45

circle
false
0
Circle -7566196 true true 35 35 230

@#$#@#$#@
NetLogo 2.0.1
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@