41J Blog

Archive for the ‘Uncategorized’ Category.

Lab workbench build notes

April 7, 2015, 9:04 pm

I’ve been setting up a new work area for my lab in Somerset. As part of this I needed to prepare some workbenches. I guess I could have bought them, but I don’t think I’d find anything that would suit my requirements at a reasonable price. So I decided to build them.

I wanted a solid bench, that would basically take anything I’d put on it. I also wanted it to be a metre deep. I tend to find that as I pile up test equipment I lose all the usable work area. By making it a metre deep I should have ample space for test equipment, and still have room to work. So the dimensions were 2 metres long by 1 metre deep.

I used this video from Mr Knackers to guide my build. I’m no woodworker, and there were some screwups along the way but I’m happy with the results. Hopefully the next bench will take less time.

My build notes follow, which will hopefully remind me what to do next time.

The bench frame is made from 2×4 whitewood timber. I bought 15 3 metre pieces on ebay though it was actually delivered by Jewsons. It cost me 100GBP delivered (~150USD). The build used 7.5 pieces, so I should have enough for 2 benches. The top is 16mm plywood which I bought from Wickes.

First I constructed the legs, I cut 4 lengths to 750mm-16 (734mm). And another 4 to 734mm-2inches (632.4mm). The 2 lengths are screwed together creating a notch for the frame to sit in. I cut the pieces out on a mitre saw. To make sure I got everything cut to the same length I clamped to pieces in, using my first as a reference like this:

Once all the legs are cut out, the two pieces are screwed together (two screws at the top, two at the bottom). I used 60mm screws for this.

You now need to cut an additional notch out of the larger piece so the frame will sit on the corner. You need to pay attention to the orientation of the legs when doing this. The remaining part of the longer piece will be on the inside of the bench. The shorter pieces should therefore all be facing out. 2 facing left, and 2 facing right. Otherwise things will look weird.

Mr Knackers suggests cutting a bunch of slots with a circular saw and then bashing them out with a chisel to cut the the longer piece down. I did this, but it was hard to get a clean finish. I’ll be looking for a new method if I do this again.

Here are the cuts made by the circular saw:

Then bashed out:

And cleaned up:

And here are all the legs with the notices cut out:

Once the legs are finished it’s time to build the frame. The outer dimensions of my frame where 2metres by 195cm as I wanted to 5cm overhang on the front for clamping things to.

The corners of the frame where cut at a 45 degree angle on the mitre saw. This gives a stronger and cleaner joint than just having the two pieces sitting at right angles.

The frame is screwed together at the corners with 4 screws. These obviously need to be offset slightly:

I found it necessary to use pilot holes everywhere.

The legs can then be installed. They are screwed in to the frame on one. Alignment is important here, and I found that the cut out section was imperfect in some places. But things fit together well enough.

Coach bolts are used on the other side to fix the legs to the other edge of the frame. I used M10 bolts, and found getting them screwed in at right angles using a cordless drill problematic. Using a right angled cut in a piece of would to align the bit as it goes in seems to help. But I wonder if there’s a better way.

Next I installed additional pieces to strengthen the bench. These were held in by 2 screws on each side:

Finally I braced the legs at the back sides. The braces are only held in place by one screw each. I removed one of the screwed used to hold the legs together and replaced it with a long screw going through the leg and into the brace. I wasn’t particularly happy with this and may add another screw here. I also added a central leg to take any weight in the middle of the bench. I felt this might be required as it’s so deep.

Finally I cut down the plywood with a circular saw, clamping a piece of wood to the plywood to align the saw. This was then glued and screwed down.

Overall I’m happy with the results and it appears to take a bunch of weight:

I plan to build another one, and when I finally get to use it may add a rubber mat covering and trim to protect the plywood.

Category: Uncategorized | 1 Comment

In-place Radix sort O(k) space overhead

March 25, 2015, 10:14 pm

The following code implements an in-place Radix sort with O(k) space overhead. It currently doesn’t deal with signed values however that should be relatively easy to add this, the high bit just needs to be sorted in reverse order.

Unlike comparison sorts Radix sort only operates on integers with a complexity linear in the terms of the number of elements in the list (n) as a multiple of the number of digits in the integer. The implementation below operates in base 2.

This implementation sorts each bit in turn starting with the most significant bit. It operates by maintaining pointers to the top and bottom (I term them left and right below) of the array shuffling those elements with one at the current bit position to the left and zero to the right. It does this by swapping elements each time it encounters a pair in the wrong place and moving the left and right pointers toward each other until they meet.

While this sorts a single bit position, in order to sort the entire array the algorithm proceeds recursively. Once the one’s and zero’s have been sorted in the current position the Radix sort proceeds to sort all the one’s for the next lowest bit, and all the zero’s for the next lowest bit separately. While most easily described recursively, the implementation keeps track of the partitions in a vector and sorts these in a loop.

The implementation below keeps track of all the bin partitions, and thus space overhead is O(2^k) where k is the number of digits. A recursive solution would possibly be more efficient, as the algorithm would not need to keep track of all partitions down to the final bit.

#include <iostream>
#include <vector>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

int bits = 32;

void dump_array(vector<int32_t> array);
void bin_dump(int32_t v);
void inplace_radix_sort_bit(vector<int32_t> &a,int start,int end,int bit,int &breakpoint);

void swap(vector<int32_t> &a,int l,int r) {

  int32_t x = a[l];
  a[l] = a[r];
  a[r] = x;
}

bool bit_is_set(int32_t v,int bit) {
  if((v & (1 << bit)) > 0) return true;
                      else return false;
}


void inplace_radix_sort(vector<int32_t> &a) {

  int breakpoint;
  vector<int> breakpoints;

  inplace_radix_sort_bit(a,0,a.size(),bits-1,breakpoint);
  breakpoints.push_back(0);
  breakpoints.push_back(breakpoint);
  breakpoints.push_back(a.size());

  for(int bit=bits-2;bit>=0;bit--) {

    cout << "breakpoints: ";
    for(int n=0;n<breakpoints.size();n++) cout << breakpoints[n] << " ";
    cout << endl;

    vector<int> newbreakpoints;
    for(int n=0;n<breakpoints.size()-1;n++) {
      if(breakpoints[n] != breakpoints[n+1])
     // inplace_radix_sort_bit(a,breakpoints[n]+1,breakpoints[n+1],bit,breakpoint);
      inplace_radix_sort_bit(a,breakpoints[n],breakpoints[n+1]-1,bit,breakpoint);
      newbreakpoints.push_back(breakpoint);
    }

    // create new breakpoint list (equiv for recursion)
    vector<int> mergebreakpoints;
    for(int n=0;n<breakpoints.size();n++) {
      mergebreakpoints.push_back(breakpoints[n]);
      if(n!=(breakpoints.size()-1)) mergebreakpoints.push_back(newbreakpoints[n]);
    }
    breakpoints = mergebreakpoints;

    // remove duplicates
    vector<int> cleanedbreakpoints;
    cleanedbreakpoints.push_back(breakpoints[0]);
    for(int n=1;n<breakpoints.size();n++) {
      if(breakpoints[n] != breakpoints[n-1]) cleanedbreakpoints.push_back(breakpoints[n]);
    }
    breakpoints = cleanedbreakpoints;
  }

}

void inplace_radix_sort_bit(vector<int32_t> &a,int start,int end,int bit,int &breakpoint) {

  // sort each bit posiiton

  cout << "sorting bit: " << bit << "  pos: " << start << " " << end << endl;
  int l_pos = start;
  int r_pos = end;

  for(;l_pos < r_pos;) {
    cout << "l_pos: " << l_pos << " r_pos: " << r_pos << endl;
    cout << "comparing: " << a[l_pos] << " " << a[r_pos] << " ";
    bin_dump(a[l_pos]);
    cout << " ";
    bin_dump(a[r_pos]);
    cout << endl;
      
    bool l_bit = bit_is_set(a[l_pos],bit);
    bool r_bit = bit_is_set(a[r_pos],bit);
    if(l_bit) cout << "l_bit: 1" << endl; else cout << "l_bit: 0" << endl;
    if(r_bit) cout << "r_bit: 1" << endl; else cout << "r_bit: 0" << endl;

    if(!l_bit &&  r_bit) { swap(a,l_pos,r_pos); l_pos++; r_pos--; cout << "swp"          << endl; if(l_pos == r_pos) if(bit_is_set(a[l_pos],bit)) {l_pos++; break;}} else
    if( l_bit && !r_bit) {                      l_pos++; r_pos--; cout << "10 linc rdec" << endl; } else
    if( l_bit &&  r_bit) {                      l_pos++;          cout << "11 linc"      << endl; if(l_pos == r_pos) {l_pos++; break;}} else
    if(!l_bit && !r_bit) {                               r_pos--; cout << "00 rdec"      << endl; if(l_pos == r_pos) { break;}}
  }
  breakpoint = l_pos;
  dump_array(a);
}

void bin_dump(int32_t v) {

  for(int n=bits-1;n>=0;n--) {
    if(v & (1 << n)) cout << "1"; else cout << "0";
  }

}

void dump_array(vector<int32_t> array) {
  
  for(int n=0;n<array.size();n++) {
    printf("%20d ",array[n]);
    bin_dump(array[n]);
    cout << endl;
  }

}

int main() {

  vector<int32_t> array;
  for(int n=0;n<20;n++) {
    array.push_back(rand());
  }

  cout << "random array" << endl;
  dump_array(array);

  inplace_radix_sort(array);

  cout << "sorted array" << endl;
  dump_array(array);
}

Category: Uncategorized | Comment

Finding the majority element in a list

March 19, 2015, 5:16 am

The problem is to find the majority element in a list if one exists. That is, return the element that occurs occupies >50% of the positions in the list. Additional constraints are that the algorithm should operate in linear time and use constant additional space ( O(N) time and O(1) space).

There are a few way of solving this problem. Initially I thought one solution might be to Radix sort the list in-place and then search for the longest run. This would certainly be linear time but in-place Radix sort it a bit of a pain.

Turns out there’s an easier solution called Moore’s Linear Time Majority Vote Algorithm. You can find a nice description here. The algorithm works iteratively. The first element is selected as the initial candidate and it’s count is set to 1. The algorithm then iterates over the remaining elements if the element matches the candidate it’s count is increased, if the count falls to zero the candidate is replaced with the current element (and the count set to 1). In this way the algorithm cancels out elements as it goes. If the element was the true majority item, then reducing the count just canceled out the non-majority element, and the element remains the majority item in the remainder of the array. If it wasn’t then we simply removed two non-majority items which does not effect the result.

The algorithm will result in a candidate, but we still need to test to make sure that it is actually the majority item. If there was no majority item canceling out “two non-majority” items above will effect the result. So we make a single pass over the array and count the number of occurrences of the candidate and test if this is >50%.

A C++ implementation of the algorithm is shown below:

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

int find_candidate(vector<int> &data) {

int candidate=0;
int count=0;

candidate=data[0];
count = 1;

for(int n=1;n<data.size();n++) {
if(data[n] == candidate) count++;
else count–;

if(count==0) {candidate=data[n]; count=1;}
cout << "count: " << count << endl;
}

return candidate;
}

int main() {

vector<int> data;

srand(time(NULL));
for(int n=0;n<10;n++) data.push_back(rand()%5);
cout << "data: ";
for(int n=0;n<data.size();n++) cout << data[n] << " ";
cout << endl;

int candidate = find_candidate(data);
cout << "candidate: " << candidate << endl;

int count=0;
for(int n=0;n<data.size();n++) if(data[n] == candidate) count++;

if(count > (data.size()/2)) cout << "Majority item is: " << candidate << endl;
else cout << "No majority item" << endl;

}

Category: Uncategorized | 2 Comments

Keyence VE7800 PCB Pics

March 18, 2015, 2:36 pm

I couldn’t really resist taking a quick look inside the SEM. The instrument connects to the host PC over USB and firewire. These go to two separate boards inside the instrument. We removed the USB connection during operation and saw that images were still being acquired. It’s reasonable to assume that the firewire connection is used for image acquisition only, and that all control signals go over the USB connection. The USB device ID is 0720:1005.

Below are some quick snaps of the PCBs for reference.