Back to Questions
1.7k
views7
comments
Parity in F#?
f#

So it turns out that we need to implement odd parity in each byte of one of our result vectors (a byte array). Can anyone suggest a good way to do this in F#?

Thanks!

.

Hello,

I'd be temped to use a tuple conisting of the byte and and the boolean representing the parity bit. This would look like:

1

let vector = [| false, 1uy; true, 2uy; false, 3uy; true, 4uy |]

Otherwise, if the bit must live in the byte itself F# supports all the bit tiwdling operators you could want and also numbers represented in binary it make it easy to understand which bits your setting/masking.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#light
let myByte1 = 0b10000010uy
let myByte2 = 0b00000011uy
let myByte3 = 0b10111110uy

let getVal x = x &&& 0b01111111uy
let getParity x = x &&& 0b10000000uy >>> 7

let printValue x = 
    printfn "Value: %i " (getVal x)
    printfn "Parity: %i" (getParity x)
    
printValue myByte1
printValue myByte2
printValue myByte3

Cheers,
Rob

By on 8/17/2007 9:07 AM ()
1
2
3
4

#light
let getVal x = x &&& 0b01111111uy
let getParity x = x &&& 0b10000000uy >>> 7

So if I'm understanding this correctly, this should be reasonable?

1
2
3
4
5
6
7
8

       let mutable odd = [||] in

    for i = 0 to valueBytes.Length - 1 do
       let vByte = valueBytes.(i) in
       let parity = getParity(vByte) in
       odd <- Array.append odd [|(vByte ||| parity)|];
    done;

I know I can compact this using a map function, but first I want to understand how it works. The getParity function computes a bitwise "and" for each shift, right?

Thanks!

By on 8/17/2007 10:11 AM ()

Well, I realized that I'm making one mistake, which is in the vByte ||| parity part. I need to toggle that bit, not just set it, I think. (Correct?)

Now, I'm not sure about how to do that without changing the rest of the byte. But you got me a step closer :)

By on 8/17/2007 10:16 AM ()

Hi,

To compute parity for byte quickly you'd usually use a lookup table.

1
2
3
4
5
6
7
8
9
10
11
12

#light

let parity' x = 
  let mutable y = 0
  for i=0 to 7 do
    y <- y ^^^ ((x &&& (1<<<i)) >>> i)
  y

let parity = [| for i in 0 .. 255 -> parity' i |]

let parity_of_array a = [| for i in a -> parity.(i) |]

Cheers,

Andy

By on 8/17/2007 11:32 AM ()

Thanks for all your help. I did get something working, but it was a lot, er bulkier? than what you folks suggested.

Thanks!

By on 8/24/2007 7:02 AM ()

Hi,

To compute parity for byte quickly you'd usually use a lookup table.

1
2
3
4
5
6
7
8
9
10
11
12

#light

let parity' x = 
  let mutable y = 0
  for i=0 to 7 do
    y <- y ^^^ ((x &&& (1<<<i)) >>> i)
  y

let parity = [| for i in 0 .. 255 -> parity' i |]

let parity_of_array a = [| for i in a -> parity.(i) |]

Cheers,

Andy

By on 8/17/2007 11:32 AM ()

Sorry ... my getParity function gets the parity bit from a byte. If want to calculate it you should use a function like this:

1
2
3
4
5
6
7
8
9
10

let calculateParity x = 
    let mutable res = (0b00000001uy &&& x)
    for index = 1 to 7 do
        res <-  res ^^^ (0b00000001uy &&& (x >>> index))
    (0b00000001uy &&& (~~~res)) <<< 7

calculateParity 0uy
calculateParity 0b1010001uy
calculateParity 0b1101001uy
calculateParity 0b1111111uy

Well thats how I think it should work according to: [link:en.wikipedia.org]

Cheers,
Rob

By on 8/17/2007 11:27 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper