; Hamming Error Detection Simulation 
; written by Teresa Carrigan, 2004 


globals [ from-number from-string start-x number-of-digits myDigits praise digits1 error-list 
        step parity bin-count-list error-found?] 
breeds [ digit arrow check ones] 
arrow-own [ state ]
patches-own [ name column ]
digit-own [ error? ]


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

; initializes variables
to setup
  locals [ current n]
  ca
  set error-found? false
  set praise ["Awesome!" "You got it!" "Right!" "Correct!" "Perfect!" "Bravo!" "Splendid!"]
  set digits1 [ "0" "1" ]
  set myDigits []  
  set n 0
  set start-x 12
  set parity "even"
  set number-of-digits 12
  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 add-space from-number " was sent using Hamming SEC (even).")
      set plabel-color white
      set name 1
    ]
  ask patch-at 6 -5
    [
      set plabel-color white
      set plabel "Was there an error in transmission?"
      set name 2
    ]
  set step 1

  setup-bits from-number
  setup-arrow

  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
    ]

end

to step1
  locals [ r p]
  explain 1 "Determine the check bits."
  set r 0
  set p 1
  while [ p <= number-of-digits ]
    [  set r (r + 1)
       explain 2 "C" + p + " goes in position " + p + "."
       make-check-bit p
       set p (2 * p)
       wait slow-motion * 3
    ]
  explain 2 "C" + p + " would go in position " + p + " - no bit in that column."
  wait slow-motion * 6
  explain 2 "So, for " + number-of-digits + " total bits, there are " + r + " check bits."
  set step (step + 1)
  wait slow-motion * 4
end

to make-check-bit [ p ]
  locals [ here-x here-y where phere-x n]
  ask patches with [ column = p ]
    [ set here-x pxcor
      set here-y pycor
    ]
  set here-y here-y - 2

  ask digit-at here-x here-y
    [
      set color yellow
    ]
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 ]
  explain 1 "C1 checks bits in positions marked ---1."
  explain 2 ""
  set check-set patches with [ column mod 2 = 1 ]
  determine-parity check-set 1
  ask ones [ die ]
  set step step + 1
end

to step4
  locals [ check-set ]
      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 2
      ask ones [ die ]
      set step step + 1
end

to step5
  locals [ check-set ]
      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 4 
      ask ones [ die ]
      set step step + 1
end

to step6
  locals [ check-set ]
      explain 1 "C8 checks bits in positions marked 1---."
      set check-set patches with [ column >= 8 ]
      determine-parity check-set 8 
      ask ones [ die ]
      set step step + 1
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  even."
      explain 2 "No error in set of bits checked by C" + ch + "."
    ]
    [ set here-parity "odd" 
      explain 1 "A one left, so parity is currently odd."
      explain 2 "Error in set of bits checked by C" + ch + "."
      set-check-bit-error ch
    ]
  wait slow-motion
end

to set-check-bit-error [ ch ]
  locals [ here-x ]
  ask patches with [ column = ch ]
    [ set here-x pxcor ]
  ask digit with [ xcor = here-x ]
    [  set error? true 
       set color red
       set label-color white
    ]
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)  " ")
        set error? false
      ] ; 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
  set error-list [ ]
  ask digit with [ error? = true ]
    [ without-interruption [ask patch-at 0 2
        [ set error-list lput column error-list ]
        ]
     ]
  ifelse length error-list = 0
    [  explain 1 "No errors detected."
       explain 2 ""
       set error-found? false
       set step (step + 3)
    ]
    [  explain 1 "Errors detected with check bits " + error-list + "."
       set error-found? true
       set step (step + 1)
    ]
  wait slow-motion
end

to step8
  locals [ col ]
  set col sum error-list
  explain 2 "Sum of error positions = " + col + "."
  wait slow-motion * 3
  ifelse col > number-of-digits
    [  explain 2 col + " > " + number-of-digits + ", so multiple errors occurred.  Can't fix."
       set step (step + 3)
    ]
    [  explain 2 "Single error in position " + col + "."
       set step step + 1
    ]
end

to step9
  locals [ col ]
  set col sum error-list
  explain 1 "Fixing error in position " + col + "."
  explain 2 ""
  flip col
  wait slow-motion
  explain 1 "Error has been fixed."
  wait slow-motion
  set step step + 1
end

to step10
  locals [ here-x ]
  explain 1 "Strip the check bits, so we can see the data."
  wait slow-motion
  ask patches with [ member? column [ 1 2 4 8 16 ] ]
    [  ask digit-at 0 -2
          [ die ]
    ]
  ask patches with [ column = 1 ]
    [ set here-x pxcor ]
  ask digit with [ xcor < here-x ]
    [   set heading 90
        repeat 4
          [  fd 1
             wait slow-motion
          ]
     ]
  ask digit with [ xcor < here-x ]
    [     
        if not any? digit-at 2 0
          [  repeat 2
                [  fd 1
                   wait slow-motion
                ]
          ]
    ]
  ask digit with [ xcor < here-x ]
    [     
    
        if not any? digit-at 2 0
          [  repeat 2
                [  fd 1
                   wait slow-motion
                ]
          ]
    ]
   ask patches with [ column > 8 ]
     [ set plabel "" ]
   explain 2 "Data = " + add-space get-number
   ask digit with [ color != white ]
     [  set color white
        set label-color black
     ]
   ask patches with [ plabel-color = green ]
     [  set plabel ""
     ]
   set step step + 1
end

to flip [ col ]
  locals [ here-x ]
  ask digit with [ color = red ]
    [  set color yellow
       set label-color black
    ]
  ask patches with [ column = col ]
    [ set here-x pxcor ]
  ask digit with [ xcor = here-x ]
    [  set color red
       wait slow-motion * 5
       ifelse label = "0 "
         [ set label "1 " ]
         [ set label "0 " ]
       set color green
       set label-color white
       ask patch-at 0 -2
           [ set plabel "Fixed" 
             set plabel-color green
           ]
    ]

end


;  do whatever step comes next, then wait until user wants to continue
to one-step
  locals [ which ]
  if step < 11
    [  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 < 11
    [ 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 add-space from-number " was sent using Hamming SEC (even).")
  explain 2 "Was there an error in transmission?"

  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 [ setup ]
  wait .5
  ask-other
  set slow-motion save-slow
end

to ask-other 
  locals [ guess target question line]
  without-interruption [ set question from-number ]
  set question add-space question
  set guess user-yes-or-no? (word add-space from-number " was sent using Hamming SEC (even).\nWas there an error in transmission?")
  set target calc
  ifelse guess = target 
    [ user-message random-one-of praise ]
    [ set line "I'm sorry, but an error "
      ifelse target
         [  set line line + "WAS detected."
         ]
         [  set line line + "was NOT detected."
         ]
      user-message line
   ]
end

to-report calc
  locals [  which-step result]
  set which-step "step" + step
  while  [step < 11]
    [ run which-step
      set which-step "step" + step
    ]
  set result error-found?
  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 Error Detection 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
386
319
558
352
slow-motion
slow-motion
0
1
0.4
0.1
1
NIL

BUTTON
78
317
141
350
step
one-step
NIL
1
T
OBSERVER
T

BUTTON
143
318
206
351
NIL
go
T
1
T
OBSERVER
T

BUTTON
209
318
272
351
NIL
quiz
NIL
1
T
OBSERVER
T

BUTTON
279
319
377
352
NIL
show-again
NIL
1
T
OBSERVER
T

@#$#@#$#@
WHAT IS IT?
-----------
This model demonstrates detection and correction of single bit errors, using Hamming SEC (single-error-correction, even parity) with eight data bits. 

HOW IT WORKS
------------
First a random 12-bit pattern is generated.  This represents either stored data or a message received, that is already in Hamming SEC.  Next the check bits are marked; they will be the bits that occupy positions 1, 2, 4, and 8.  

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.  

Next we check the parity of each check bit group.  If any group has odd parity, we know that there is an error in one of the bits in that group, and we mark its check bit in red.

After checking every check bit group, if there are no red check bits, then no error occurred and we can just strip the check bits to get the data.  If there was an error, we add the position numbers of all the red check bits to get the position of the bit that has been flipped.  If the sum of the red check bit positions is greater than the number of bits we have, then multiple errors occurred and we cannot fix the error.  Otherwise, we simply flip the erroneous bit, and then strip the check bits to give the correct data bits.

HOW TO USE IT
-------------
The setup button generates a random 12-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 and ask you to determine whether or not an error in transmission is detected. 

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.


THINGS TO NOTICE
----------------
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.

In order to use the original data, we must not only correct any possible error but also strip the check bits to get the original data back.

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

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 the user to input the starting bit pattern.

Allow for a different number of data bits, set by a slider.

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 Error Detection, Hamming Code Simulation


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 Error Detection 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
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@