Serge's World

UPC-5 is a variation on the UPC-A barcode](/programming/2009/10/barcodes-in-csharp-upca) designed to contain 5 digits of data.

The checksum (or parity) for the UPC-5 format is used only to encode the barcode, and therefore is not coded directly.

Calculating the parity uses the same modulo 10 method as the UPC-A, except that the weightings are different. Odd-numbered positions are weighted 3, while even-numbered positions are weighted 9.

Once we have the weighted sum, we apply a modulo 10 to the weighted sum, which gets the remainder after applying a modulo of 10 to the weighted sum.

The parity is then 10 - (modulo 10 of the weighted sum).

UPC-5 only has a left guard and centre guard (which is places after the third digit), which are encoded as 1011 and 01 respectively.

The 5 digits are then encoded using either odd or even encoding, which is determined by the parity string.

The odd and even encodings are the same as the ones for the UPC-E format</p>

Read More »

The MSI barcode, which also goes by the name of the Modified Plessey barcode is mainly used for inventory control in places such as warehouses.

This barcode format can encode any number of digits, and is ended by a checksum digit.

The checksum digit can be calculated using one of several methods.

Using the Modulo 10 method, moving through the string in reverse, you double the value of every second digit, starting at the rightmost digit, and then add the digits together. We then take a modulo 10 of this number, subtract it from 10. This then gives the checksum digit.

For the Modulo 11 method, you need to reverse the digit string first, and then apply a weighting to each digit. There are two ways to work out the weighting. The IBM method assigns a weighting of 2, 3, 4, 5, 6, 7 to successive digits, whereas the NCR method assigns a weighting of 2, 3, 4, 5, 6, 7, 8, 9 to each successive digit. Then, taking the weighted sum, the parity is found by taking the modulo 11 of this sum, and subtracting from 11.

The remaining two methods, Modulo 1011 and Modulo 1110, first applies the one method and then the other.

Now that we have the full string with the parity digit, we can encode.

The left guard of the barcode is 110 and the right guard 1001.

There is only one encoding per digit, which makes encoding rather easy.

The UPC-E barcode format is a compressed form of the UPC-A format and is used where space is at a premium. The UPC-E format also require that there are at least 5 0’s in a group in the barcode, so that it can be compressed.

Before we shorten the barcode, we need to enter a full 11 digit UPC-A barcode (excluding the parity digit), and then calculate the parity digit as per the UPC-A barcode.

We first need add up the 11 digits of the barcode with the weighting applied. The weighting is the same as the EAN-13 and UPC-A weighting, where the weighting of each digit which is in an odd-numbered position is 1 and for even-numbered positions, the weighting is 3. To find the sum, we need to multiply each digit by its weighting before adding it together.

Once we have the weighted sum, we apply a modulo 10 to the weighted sum, which gets the remainder after applying a modulo of 10 to the weighted sum.

The parity is then 10 - (modulo 10 of the weighted sum).

Now that we have an 12 digit number, we need to shorten it to an 8 digit number.

The rules for this are quite simple.

The manufacturer portion of the number is the first 5 digits excluding the first digit of the barcode. The product portion is the subsequent 5 digits.

If the last 3 manufacturer digits are 100, 200 or 000, then the shortened for is made up of the first digit, the first two digits of the manufacturer, the last 3 digits of the product, the third digit of the manufacturer and finally the parity.

Otherwise, if the last two digits of the manufacturer is 00, then the barcode is made up of first digit, the first three digits of the manufacturer, the last 2 digits of the product, the number 3, and finally the parity.

Then, if the last digit of the manufacturer is 0, the barcode is made up of first digit, the first four digits of the manufacturer, the last digit of the product, the number 4, and finally the parity.

We can now use this number for the rest of the calculation

We do not split up this format, and only have with a guard bar at the beginning and end of the barcode. The left guard bars are encoded as 101, while the right guard bar is 010101.

The first digit of the barcode determines the parity set to use. The encodings are split up by odd and even encodings, which is determined by the parity bit. This is found by choosing the correct parity set encodings, and then finding the parity bit string for the parity we calculated earlier, and then returning the bit value at the position in the string for the digit we wish to encode.

UPC-2 is a simpler variation of the UPC-5 barcode designed to contain 2 digits of data.

The checksum (or parity) for the UPC-2 format is used only to encode the barcode, and therefore is not coded directly, and out of all the UPc barcodes, is the only one in this series which does not use modulo 10.

The parity is simply the two digits treated as an integer and then applying modulo 4 to it, and the remainder is the parity.

Like with UPC-5, UPC-2 only has a left guard and centre guard (which is places after the third digit), which are encoded as 1011 and 01 respectively.

We then apply the odd or even encoding based on the parity string we determine from the parity

The odd and even encodings are the same as the ones for the UPC-5 format.

The UPC-A barcode format is very similar to the EAN-13 barcode and is mostly used in America, although in recent years, the US is moving towards the EAN-13 format too. The UPC-A format is 12 digits long, with the last digit being the checksum (or parity) digit.

To calculate the parity for UPC-A, we use the same process as with the EAN-13 barcode. We first need add up the 11 digits of the barcode with the weighting applied. The weighting is the same as the EAN-13 weighting, where the weighting of each digit which is in an odd-numbered position is 1 and for even-numbered positions, the weighting is 3. To find the sum, we need to multiply each digit by its weighting before adding it together.

Once we have the weighted sum, we apply a modulo 10 to the weighted sum, which gets the remainder after applying a modulo of 10 to the weighted sum.

The parity is then 10 - (modulo 10 of the weighted sum).

Now that we have an 12 digit number, we can encode it.

We split the UPC-A barcode into 2 blocks of 6 digits each, with a guard bar at the beginning and end of the barcode and one in the middle of the barcode too. The end guard bars are encoded as 101, while the middle guard bar is 01010.

In the EAN-13 barcode format, the parity digit was not encoded directly, with only the first 12 digits being encoded, whereas with UPC-A, all 12 digits are encoded, including the parity. This simplifies the encoding process, since we do not have to worry about odd and even parity encodings.

The left hand side encodings are identical to the left hand odd parity encodings from EAN-13.

These encodings ensure that UPC-A forms a subset of the EAN-13 barcode.

The right hand side encodings (the last 6 digits) are the same as the right hand codings of EAN-13. The encodings are as follows:

The EAN-8 barcode format is a compressed format of the EAN-13 barcode, only containing 7 digits plus one checksum digit, and is generally used in places where a fullsized EAN-13 barcode would not fit.

To calculate the parity, we use the same process as with the EAN-13 barcode. We first need add up the 7 digits of the barcode with the weighting applied. For the EAN-8 barcode, the weighting of each digit which is in an odd-numbered position is 1 and for even-numbered positions, the weighting is 3. To find the sum, we need to multiply each digit by its weighting before adding it together.

Once we have the weighted sum, we apply a modulo 10 to the weighted sum, which gets the remainder after applying a modulo of 10 to the weighted sum.

The parity is then 10 - (modulo 10 of the weighted sum).

Now that we have an 8 digit number, we can encode it.

Like EAN-13, we split up the 8 digits we need to print into two blocks of 4 with a guard bar at the beginning and end of the barcode and one in the middle of the barcode too. The end guard bars are encoded as 101, while the middle guard bar is 01010.

The main difference now is that the parity digit is included in the barcode itself, rather than used to change the encoding, so it is remarkably simpler to implement.

For first 4 digits (the left hand side of the barcode) are encoded with the following encoding, which are the same as the odd parity encodings for the left hand side of EAN-13:

The right hand side encodings (the last 4 digits) are the same as the right hand codings of EAN-13. The encodings are as follows:

The EAN-13 barcode format is the standard barcode used on everyday products across the world, except in the US, where the UPC-A barcode is more popular.

The EAN-13 barcode is a 13 digit barcode, where the first two or three digies are the country code where the manufacturer of the product is registered. The next nine or ten digits are data digits, which adds up to 12 digits. The last digit is the checksum digit.

To calculate the checksum (also known as the parity), we first need add up the 12 digits of the barcode with the weighting applied. For the EAN-13 barcode, the weighting of each digit which is in an odd-numbered position is 1 and for even-numbered positions, the weighting is 3. To find the sum, we need to multiply each digit by its weighting before adding it together.

Once we have the weighted sum, we apply a modulo 10 to the weighted sum, which gets the remainder after applying a modulo of 10 to the weighted sum. The parity is then 10 - (modulo 10 of the weighted sum).

Now that we have a 13 digit number, we can encode the data we need to print out a barcode. Each digit is represented by a series of bars and spaces. I will represent a bar as 1 and a space as 0 for the rest of the tutorial.

EAN-13 splits up the 12 digits we need to print into two blocks of 6 with a guard bar at the beginning and end of the barcode and one in the middle of the barcode too. The end guard bars are encoded as 101, while the middle guard bar is 01010.

The parity of the barcode is not printed directly, but is rather used to determine which set of encodings we are going to use for each character, which complicates the encoding of the barcode slightly.

For first 6 digits (the left hand side of the barcode) there is an odd and even encoding. The parity defines which encoding to use. The parity check has a 6 digit binary string, where each digit determines whether to use the odd or even encoding set at the position in the parity string. So for example, for a parity of 3, the binary string is 110001, which means that at position 2, we need to use the odd set, and at position 3 we need to use the even set, and so on.

The parity encodings are as follows:

For the left hand side encodings then, the encodings are as follows:

The right hand side encodings (the last 6 digits) do not need this and are just encode straight. The encodings are as follows:

In my last post I created a binary tree class. This post follows on from that, so I would recommend reading that first, if you have not already done so.

There are three types of traversals that are generally used to traverse a tree. These are preorder, inorder and postorder traversals, and all are similar to each other, except for the order in which the operations are performed.

For the preorder case, we first get the value of the node (starting at the root), and then recursively move down the left branch of the tree, and the recursively move down the right branch of the tree.

public string preOrderTraversal(int nodeId)
{
	string str = "";

	str += (string)(((BinaryNode)nodes[nodeId]).getValue());
	if (((BinaryNode)nodes[nodeId]).getLeftChildId() != -1)
	{
		str += preOrderTraversal(((BinaryNode)nodes[nodeId]).getLeftChildId());
	}
	if (((BinaryNode)nodes[nodeId]).getRightChildId() != -1)
	{
		str += preOrderTraversal(((BinaryNode)nodes[nodeId]).getRightChildId());
	}
	return str;
}

Binary trees are a very useful data structure, and are used in things like data storage, and parsing of mathematical expressions. Implementing a binary tree is C# is not hard at all.

The first thing we need to do is define a class for the node of the tree. BinaryNode. This contains four variables: value which is an object containing whatever data you have set the node to. leftChildId and rightChildId are the ids of the child nodes linked to this node. parentId is the id pf the parent node to this node, and is not strictly necessary, but it does make modifying the tree much simpler - and more efficient.

The rest of the class is purely functions to get and set these values.
Read More »

A prime number is any number that can only be evenly divided by itself and 1. So for example 2, 3 and 5 are prime, but 6 and 9 are not.

Now, to find all the prime numbers that are factors in a number, we need to first check if the number is even. If it is, then 2 is a factor, and then we keep dividing until the number is odd.

Then, starting at 3, and counting up in 2′s, we try and find a number which divides into the number, each time dividing by the divisor if a match is found.

using System.Collections;  
  
public static List<long> PrimeFactors(long val)
{
	List<long> factors = new List<long>();

	while (val % 2 == 0)
	{
		factors.Add(2);
		val = val / 2;
	}

	long divisor = 3;
	while (divisor <= val)
	{
		if (val % divisor == 0)
		{
			factors.Add(divisor);
			val = val / divisor;
		}
		else
		{
			divisor += 2;
		}
	}
   
	return factors;
}

The full sourcecode for the MathLib library is available at https://github.com/sjmeunier/mathlib

Originally posted on my old blog, Smoky Cogs, on 23 Oct 2009

Updated 5 Oct 2016: Updated code snippet after refactoring MathLib library