Multiple hall effect sensors in proximity

Update from OP.
Current: Needs to be no more than 30mA.
Distance: A 4mm air gap.
Minimum data rate: Around 256Bits/second. Size: Needs to be as small as possible.(Must fit into 5x10x5mm spot)
Cost: Looking to keep it under $1.50

Is that 30 mA receive or 30 mA transmit.
Unidirectional?
Cost of $1.50 covers what? TX & RX, just one (which?),Hall cell in that price.
How many? 1 10? 100? 100,000?
MUCH more information allows us to provide a single instant answer without playing death of 1000 cuts / iterations.

The Hall cell chosen is completely unsuitable for this task.
This is because it is a sampling type which sleeps for most of the time and wakes to take a reading occasionally.
Th data sheets hows that it has a 0.1% on time and 99.9% off time.
Cycle time is 45 to 90 ms and on time is 45 to 90 uS.
So you can only signal at most at 1 bit per on time if you are careful or at about 10 bps max and probably less.

There are many Hall cells available which are not the sampling type and low enough current.

[This is Digikeys cheapest at about 58c/1.]http://www.semicon.toshiba.co.jp/docs/datasheet/en/Sensor/TCS20DPR_en_datasheet_110207.pdf)
This has 4.4 mT sensitivity worst case.
Mutiply T by 10,000 to get Gaus.
4.4 mT x 10,000 = 44 Gauss = about te same as before.

Doable at range and size specified. Implementation details depend on all answers not yet known.

More when more known ...

This question is eminently answerable but rather than giving you a single "this will work" answer, having more information will lead to a much better answer. What range do you want to work over from the face of the Hall cell to the face of the inductor?
Is there anything in the way obstructing, spinning, cutting ...?
Is it in seawater, embedded in a block of steel or a lava field, ...?
What maximum data rate do you require?

Be as specific as possible re constraints on cost, size, and anything else you can hink of. DO NOT have us say xxx meets your needs and then say "Oh, but it must be British Racing Green and work at 2000 feet underwater" or whatever :-)

Don't let the following worry you. The answer is a piece of ferrite and some wire - but this is "what lies underneath":

IF there is a need to wind a coil and activate the sensor at a distance, then it may come down to formulae like this:

Relating to an inductor like this:

(http://www.netdenizen.com/emagnet/solenoids/thinsolenoid.htm)
From here

Or it's big brother which has finite thickness, from here

BUT probably not.

Adding a core increases the field by the permeability of the core - but, we'll come to that.

FWIW those formulae are about the nicest I've seen for a common problem that usually get's a horrendously complex answer. This is mainly geometry. Most analyses are for the field INSIDE the solenoid and few deal with it beyond the ends.

I've used the Allegro 3503 ratiometric linear sensor. It's discontinued, but I suspect its similar to the 1301/1302 sensors. It is very linear when positioned between two opposing magnets. This particular config (push-push mode) is shown on page 27 of the guide that you can download at http://www.allegromicro.com/en/Design-Center/Technical-Documents/Hall-Effect-Sensor-IC-Publications/Hall-Effect-IC-Application-Guide.aspx, but there are some other interesting modes. Give that ref a good read. You are talking mm here, and not cm. I think if you have a small 1 mm range, you can probably get 0.5 mm resolution, but I can't say I've pushed it that far. Strong neodymium magnets would certainly help.

They're even easier to use than you describe. The output voltage simply changes as a function of flux density.

As a design alternative, you might consider an optical position sensitive detector from Hamamatsu. You'd just need a 1-D sensor. They're good to about 50 microns over two millimeters.