A Beginner’s Guide to Binary Heaps

Introduction to Binary Heaps

Today, we will discuss a binary heaps, a common data structure in programming. Heaps have multiple uses in programming including:

  • Priority Queues: a queue-like data structure which has a priority field as a key. In a priority queue implemented with a min-heap, the element with the lowest value for priority will the next available element. In a priority queue implemented with a max-heap, the element with the highest value for priority will be the next available element.
  • Finding the k’th [small/larg]est element: Heaps are really good at solving this problem, because after creating a heap from the target elements, the lowest (min-heap implementation) or the highest (max-heap implementation) values can be extracted with ease.

Heaps are very useful when you need to retrieve the max (max-heap) or min (min-heap) quickly (\(O(\log n)\)), need to add an element with a certain value quickly (\(O(\log n)\)), and need to be able to build the structure quickly (\(O(\log n)\)).

Continue reading A Beginner’s Guide to Binary Heaps

Artificial Finger

Introduction

I was thinking, how do we determine what we are touching when we aren’t looking at our fingers? I realized that our nerve endings are very sensitive and can feel some of the lightest vibration. It also dawned on me that perhaps the texture on our fingers – our fingerprints – vibrate differently when feeling a different surface.

Why Does This Matter?

Physiology

Understanding how we are able to sense our environment is important for many reasons. Perhaps, if we determine the sequence of action potentials that take place when we feel a material, we may be able to develop an electro-mechanical transducer for prosthetics.

More importantly, we get to better understand our senses.

Robotics

A large portion of robotics surrounds the field of “localization,” the process through which a device captures, processes and understands the environment it is in. In the future, a robot could be built, which learns its surroundings by touching materials and taking pictures of them.

The Sensor

Our fingerprints composed of many ridges in a random, but organized pattern. If you place your finger carefully on a surface, without rubbing it at all, while not looking, you cannot determine what surface you are touching. But as soon as you rub the surface, you can feel vibrations that determine physical properties such as smoothness of the surface.

You can also determine the flexibility of a surface by applying a constant pressure to it, but determining how far in your finger moved.

The actual sensor consists of a motion sensor that can determine vibrations, as well as position, and an air pressure sensor to determine contact pressure. These sensors are placed within an inflated, air-tight chamber such that any external pressure on this chamber will cause a rise in the internal air pressure. This can be measured by the air pressure sensor.

A picture of how this sensor could look is below.

Front:

Side:

Bottom (External):

Build Guide

At the bottom of the finger, to the IMU, there is a mechanical link. If the sensor is just suspended inside the air chamber, very little vibrations will be transmitted into the IMU.

The PCB should be made of a flexible material like DuPont Pyralux. This will allow the sensors to move in the finger, constrained by the mechanical link.

The airtight bag should be heat sealed around the PCB. If this bag loses air, the sensor may not work properly. An alternative would be to use a different type of a pressure transducer. Air pressure sensors are very cheap, but there are many types of flexion sensors.

My Prototype (Under Development)

The prototype will currently only have an IMU. For the IMU, I will be using a six axis IMU from ST Microelectronics, the LSM6DSM. It has a 16 bit resolution for its accelerometer and gyroscope axes. Its accelerometer is capable of about 5k samples per second per axis. Its gyroscope can handle 1.5k samples per second per axis.

The main processor for this project will be an ESP32 by Espressif Systems. It’s a dual core, 240 MHz CPU with WiFi and Bluetooth. I am using a prebuilt module, the esp32-wrover. I chose the esp32-wrover module because it has an extra 32 Mbit of external SRAM, allowing for a significantly larger capture buffer. The ESP32 can capture and send its data over WiFi to a computer running data acquisition software, or directly onto a server.

The main processor board has a 32 GB SD card for headless data acquisition and a Lithium polymer PMIC for power.

See ya next time!

KiCAD Introduction

Introduction

I am currently trying to understand how to use KiCAD. KiCAD is a complete open source schematic capture and PCB design toolkit, supported by CERN. To begin, one of the pros of KiCAD is that it runs on most common operating systems – Linux, Windows and Macintosh.

With the purchase of Eagle, the industry-standard PCB design software, by Autodesk, and the shift to a subscription-based license, there has been significant development in both the software and the community.

Since KiCAD is new to me too, I will use this blog as a beginners guide.

Installation

I am running KiCAD on Windows 10 currently. The installation was rather straightforward. I downloaded and ran the KiCAD installer from KiCAD’s homepage. Within no time, it was installed. I also installed Wings3D, the optional 3D toolkit recommended for installation. I’m assuming it is required for KiCAD to render 3D models. However, for 3D CAD, my go-to software is Autodesk Inventor Professional, or Fusion 360.

First Run

I ran KiCAD for the first time and created a project. To create a project, use the file menu, select “New Project” and then select “New Project.” Now, you need to select the directory to save all of the KiCAD project files in, and name the KiCAD project file (*.pro). The name of this file is the name of the project. Below is a screenshot of what it should look like:

In orange, is circled the menu. The buttons in green allow you to create or open a project. In purple, is a navigator, which shows the hierarchy of the project. In red is a set of buttons which allow you to open different tools.

First Impressions

My first impressions of KiCAD is that it is a rather complex tool to use. Instead of being built as a single, well-connected applications, it is a set of individual applications, or components, which have been selected and chosen to interact with each other. This is a little unnatural to me.

Schematic Capture

KiCAD comes with a schematic capture tool, Eeschema. It seems to have all the major features required to draft a circuit’s schematic.

On the right, is a set of tools we can use to create our schematic. At the top is a cursor button, the main tool which allows us to select components. Upon hovering over many buttons and options, and sometimes even written on the button, are keyboard shortcuts which allow faster development.

The arrow keys move the cursor around, with the grid – one point at a time. It seems as though KiCAD is designed to allow minimal mouse usage. That’s always a plus!

We have two maroon buttons on the right side – “Place component” and “Place power port.” We cal also place wires, buses, junctions, not-connected, net names, global labels, hierarchical labels, hierarchical sheets, hierarchical pins, lines/polygons, text and bitmaps. I do not know what most of these buttons do, but we will likely find out while using KiCAD.

Placing Components

To place components, we can use the “Place component” dialog, click on the schematic to select a target location, select a component and then use the cursor to finally place it.

The “Filter” field seems to allow me to search for a component I want. The size of the bundled library is very small. It will be necessary to create schematic symbols and footprints for most components! All the common components and passives seem to be in the “device” library.

I placed a battery and a few passives on my schematic sheet. To place a component, align your cursor to where you want to drop the component, and left-click or press enter.

Here’s how my schematic looks:

Keyboard Shortcuts in Eeschema

Upon scouring through the menus in KiCAD’s Eeschema, I found quite a few useful keyboard shortcuts:

  • Move component: M
    • Drag component: G
    • Move literally moves a component, disconnecting everything connected to it. Drag moves the connections with the component.
  • Rotate clockwise: R
  • Delete component: [delete]
  • Copy: C
  • Add component: A
  • Add power port: P
  • Place wire: W
  • Junction: J
  • Label: L

While most keyboard shortcuts are capitalized (use shift when pressing these keys), KiCAD seems to perform the correct action when pressing the lowercase key. Perhaps this is a bug, or a feature.

Random Tidbits

I really like how in Eeschema moves your cursor back to where it was before trying a command, when a command finishes. If you are placing components next to each other, for example, you could use the arrow keys to move the cursor, say, two grid spaces, and issue another command. It’s also really efficient being able to control the cursor with arrow keys. As a programmer, I am much more efficient and fast at typing than using a mouse.

In Conclusion

I’ve now covered basics on the KiCAD schematic tool, Eeschema. In the next blog post, we can try to dive deeper and design something cool with it. So far, I’m impressed with KiCAD. At a first sight, it seems like an under-developed tool, but when you try using it, it’s filled with features that make working with schematics so much easier. The best part is that KiCAD is open source, and may be used for commercial projects – something that most other free electronics CAD software lack.

See ya next time!

I’m Designing an EEG!

I’m designing an EEG from scratch as a prototype for a startup! It’s a very ambitious project, as I am very rusty at electronics. My goal is to design a very simple, inexpensive, versatile, easy-to-use and self-contained device, which confirms to medical standards (though FDA approval isn’t a goal for this project).

I cannot disclose the feature set of this device, or the problem this aims to solve. However, I will try my best to use this blog as a journal for the project.

Since I can be classified as a “noob” in electronics/electrical engineering, this blog will be a great resource for those who are getting their feet wet in electronics. This blog is a tool for me to communicate what I learn, and what traps I run into while working on this project, and how to avoid them.