2
\$\begingroup\$

I have a project in which I have 102 8-bit PISO shift-registers in daisy chain configuration and they are outputting to a common SDI line connected to a PIC32MX controller.

There is a total of 816 bits I need to read and store in the memory so I can manipulate the data being read. Also, I'll have to read them 34 times because the application requires that I XOR those 816 bits for each of these read operations.

I have two questions:

  • How would you store the data? I'm worried because I'll have quite a bit of data to handle and I'm trying to optimize processing to the very minimum. Note that I need to be able to extract the (row, col) indexes so I can compute other values accordingly.
  • After XORing the data, I'll need to traverse the structure and find occurrences of '0's. What do you suggest in terms of search algorithm?

I was thinking of creating a matrix with [34,816] dimension and sequentially XOR the rows to a single, 816 column array and then search for '0's in the array, but I'm not sure how to do it, any thoughts?

\$\endgroup\$
5
  • \$\begingroup\$ So you have 102 CS lines? This sounds more like a general programming problem not related to electronic design. I recommend it be moved to stackoverflow.com, where you might get better advise on algorithms. \$\endgroup\$ – tcrosley Mar 17 '14 at 16:15
  • \$\begingroup\$ @tcrosley, I tend to agree, although I decided to post it here due to the implications of programming in a PIC architecture. How could I move the question there? \$\endgroup\$ – Joum Mar 17 '14 at 16:18
  • \$\begingroup\$ All of the shift-registers output to the same line, one bit at a time. I select which shift-register is active at each time with Johnson counters. I'll be reading from one pin only, but that isn't my problem, the memory handling and search algorithm are... :) \$\endgroup\$ – Joum Mar 17 '14 at 16:24
  • \$\begingroup\$ I was just curious about the CS's. I flagged this for moderator attention. \$\endgroup\$ – tcrosley Mar 17 '14 at 16:26
  • 2
    \$\begingroup\$ I think this question is tied closely enough to embedded programming that it should stay hee for now. \$\endgroup\$ – Dave Tweed Mar 17 '14 at 16:29
3
\$\begingroup\$

To process the bits as efficiently as possible, you're going to want to keep them packed into 32-bit words whereever it makes sense. 816 bits is 25.5 words, which really isn't bad at all.

To search for ones efficiently, break the task into two steps: Check entire words for non-zero in the outer loop, then search for individual bits in the words that aren't all-zero in the inner loop.

One trick that can be used to isolate individual bits in a word that has multiple bits set is to AND the word with its negation (2's complement). The result has just a single bit set — the rightmost 'one' in the original word. You can then use this result to clear that bit and look for the next 'one'.

In C:

temp = word & -word;
word &= ~temp;

For example, suppose your 32-bit word contains 0x40010080:

01000000000000010000000010000000  original word
10111111111111101111111110000000  ... negated
00000000000000000000000010000000  ... and then ANDed together

11111111111111111111111101111111  complement of previous word
01000000000000010000000000000000  ... ANDed with original word for next iteration

EDIT:

The efficiency of this algorithm comes from the fact that you only iterate once for each 'one' (three of them in this example), rather than once for each of the 32 bits in the word. This is a huge advantage if you're doing something like simply counting the 'one's. The downside is that it doesn't give you the bit index directly, but there are ways to accelerate that as well. For example, to get the bit index of a single bit set in a word, you could use a binary encoding algorithm:

index = 0;
if (word & 0xAAAAAAAA) index += 1;
if (word & 0xCCCCCCCC) index += 2;
if (word & 0xF0F0F0F0) index += 4;
if (word & 0xFF00FF00) index += 8;
if (word & 0xFFFF0000) index += 16;

The overall advantage of the two algorithms above, as compared to a brute-force iteration through the bits, depends on how many bits you expect to find in each word. If they're rare (less than about 4 per word), then these algorithms should be faster. If they're more common than that, just go with the iterative loop:

for (index = 0, mask = 0x00000001; index < 32; ++index, mask <<= 1) {
  if (word & mask) {
    /* do your processng here */
  }
}
\$\endgroup\$
7
  • \$\begingroup\$ I'm sorry but I couldn't follow you regarding your last paragraph (not a native english speaker). Can you elaborate? \$\endgroup\$ – Joum Mar 17 '14 at 16:49
  • \$\begingroup\$ Thank you for your quick reply! I got what you meant now, but I still don't understand how this adds efficiency. Do I really need this operation? I was thinking of simply calculating the index (up to 816) if a certain 32-bit word's value were bigger than 0 - don't you think it's faster? \$\endgroup\$ – Joum Mar 17 '14 at 17:04
  • \$\begingroup\$ Also, I meant finding '0's not '1's. \$\endgroup\$ – Joum Mar 17 '14 at 17:21
  • 1
    \$\begingroup\$ For finding zeros, you can still use this algorithm, just invert the data first (or, if the data you're XORing with is fixed, just invert that). The efficiency of this algorithm comes from the fact that you only iterate once for each 'one' (three of them in this example), rather than once for each of the 32 bits in the word. This is a huge advantage if you're doing something like simply counting the 'one's. The downside is that it doesn't give you the bit index directly, but there are ways to accelerate that as well. Are you going to be programming in C or assembly? \$\endgroup\$ – Dave Tweed Mar 17 '14 at 18:11
  • \$\begingroup\$ Thank you again for your help! I'll be programming in C. Can you please share some insight on how you would implement such an algorithm? \$\endgroup\$ – Joum Mar 18 '14 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.